程序员经验分享-hwhale

有人可以解释一下 Big-Oh 如何与求和一起使用吗？

2023-11-22

我知道这严格来说不是一个编程问题，但它is一个计算机科学问题，所以我希望有人能帮助我。

I've been working on my Algorithms homework and figuring out the Big-Oh, Big-Omega, Theta, etc, of several algorithms. I'm proving them by finding their C and N0 values and all is going well.

然而，我遇到了该集中的最后两个问题，并且我正在努力弄清楚如何解决它们（谷歌并没有多大帮助）。

我以前不需要计算出总和的大哦/欧米茄。

我的最后两个问题是：

  • Show that Σ (i=1 to n) of i2 is O(N3)

and

  • Show that Σ (i=1 to n) of [log2i] is Ω(n log n)

我的问题是，我该如何证明这一点？

For example, in the first one, intuitively I can't see how that summation of i2 is O(N3). The second one confuses me even more. Can someone explain how to show the Big-Oh and and Big-Omega of these summations?


My guess is that what the question statement means is if you're summing the results of some calculation for which the running time is proportional to i2 in the first case, and proportional to log2i in the second case. In both cases, the running time of the overall summation is "dominated" by the larger values of N within the summation, and thus the overall big-O evaluation of both will be N*O(f) where f is the function you're summing.

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Math

computerscience

bigo

有人可以解释一下 Big-Oh 如何与求和一起使用吗？ 的相关文章

  • Java中如何对整数除法进行四舍五入并得到int结果？ [复制]

    这个问题在这里已经有答案了 我刚刚写了一个小方法来计算手机短信的页数 我没有选择使用Math ceil 老实说 它看起来很丑陋 这是我的代码 public class Main param args the command line arg

  • 处理中渲染极地带面体时出现问题

    我最近一直在研究 Zohedrons 和Rob Bell http zomadic com 做出了美丽的 我玩了免费的极地带面体 Sketchup 插件 http zomebuilder com 并考虑使用几何图形加工 http proce

  • 如何求解：T(n) = T(n - 1) + n

    我已经解决了以下问题 T n T n 1 n O n 2 现在 当我解决这个问题时 我发现界限非常松散 我是否做错了什么 或者只是这样 您还需要一个递归关系的基本情况 T 1 c T n T n 1 n 为了解决这个问题 您可以首先猜测一个

  • 使用C标准数学库精确计算标准正态分布的CDF

    标准 C 数学库不提供计算标准正态分布 CDF 的函数 normcdf 然而 它确实提供了密切相关的函数 误差函数 erf 和互补误差函数 erfc 计算 CDF 的最快方法通常是通过误差函数 使用预定义常量 M SQRT1 2 来表示 d

  • 在 C# 中存储矩阵值的快速且有用的方法

    我需要用 C 为 3D 引擎创建一个 4x4 矩阵类 我见过一些其他引擎将矩阵值存储在单个浮点成员变量 字段中 如下所示 float m11 m12 m13 m14 float m21 m22 m23 m24 float m31 m32 m

  • 寻找将集合映射到整数的双射函数

    对于任意两个序列 a b 其中 a a1 a2 an 且 b b1 b2 bn 0a b具有相同的元素 而不关心它们的顺序 例如 如果 a 1 1 2 3 b 2 1 3 1 c 3 2 1 3 则 f a f b f a f b 我知道有

  • 我们如何计算这段代码片段中缓存的读取/未命中次数？

    鉴于我目前正在学习的这本教科书中的代码片段 Randal E Bryant David R O Hallaron 计算机系统 程序员的视角 第 3 版 2016 年 Pearson 全球版 因此本书的练习可能是错误的 for i 31 i

  • 带 If 的嵌套 For 循环的时间复杂度

    void f int n for int i 1 i lt n i if i int sqrt n 0 for int k 0 k lt pow i 3 k do something 我的思考过程 执行if语句的次数 sum i 1 to

  • C 埃及分数

    古埃及人仅使用以下形式的分数1 n因此任何其他分数都必须表示为这些单位分数的总和 而且 所有单位分数都是不同的 在C或Java中使任何分数成为埃及分数 总和越少越好 的好方法是什么 可以使用什么算法 分支定界 a 例如 3 4 1 2 1

  • 两个整数乘积的模

    我必须找到c c a b mod m a b c m 是 32 位整数 但 a b 可以超过 32 位 我正在尝试找出一种计算 c 的方法 而不使用 long 或任何 gt 32 位的数据类型 有任何想法吗 如果m是质数 事情可以简化吗 注

  • GCC的sqrt()编译后如何工作？使用哪种root方法？牛顿-拉夫森？

    只是对标准感到好奇sqrt 来自 GCC 上的 math h 我自己编码的sqrt 使用牛顿拉夫森来做到这一点 是的 我知道 fsqrt 但CPU是如何做到这一点的呢 我无法调试硬件 现代 CPU 中的典型 div sqrt 硬件使用 2

  • 如何四舍五入到一半，始终为正方向？ [关闭]

    很难说出这里问的是什么 这个问题是含糊的 模糊的 不完整的 过于宽泛的或修辞性的 无法以目前的形式得到合理的回答 如需帮助澄清此问题以便重新打开 访问帮助中心 help reopen questions 如何实现以下舍入 0 0126083

  • 为什么 C# Math.Ceiling 向下舍入？

    我今天过得很艰难 但有些事情不太对劲 在我的 C 代码中 我有这样的内容 Math Ceiling decimal this TotalRecordCount this PageSize Where int TotalRecordCount

  • CGPoint 标量乘法 Swift

    我正在 SpriteKit 中构建一个平台游戏 并将为我的实体实现更新功能 以便它们根据重力和速度移动 但是 我需要使添加的速度量与增量时间成比例 以防止帧速率影响我的实体的移动方式 因此我将导入 GLKit 以便我可以使用标量函数 但是

  • 什么是拉姆达？

    有人可以很好地描述什么是 Lambda 吗 我们为它们设置了一个标签 它们涉及 C 问题的秘密 但我还没有找到一个很好的定义和解释来解释它们是什么 闭包 lambda 和匿名函数不一定是同一件事 匿名函数是任何没有 或者至少不需要 自己名称

  • 将 z 分数转换为百分比的函数

    谷歌不想提供帮助 我能够计算 z 分数 并且我们正在尝试生成一个函数 给定 z 分数 可以得出正态分布中低于该 z 分数的人口百分比 我能找到的只是对百分比表的 z 分数的引用 有什么指点吗 Is it 这个 z 分数 链接 http en

  • 在 2D 中将一个点旋转另一个点

    我想知道当一个点相对于另一个点旋转一定角度时如何计算出新的坐标 我有一个块箭头 想要将其相对于箭头底部中间的点旋转角度 theta 这是允许我在两个屏幕控件之间绘制多边形所必需的 我无法使用和旋转图像 从我到目前为止所考虑的情况来看 使问题

  • PHP 负面因素不断增加

    我这里有这个代码 remaining 0 foreach clientArrayInvoice as key gt row remaining remaining row total 它的作用是 它获取总计值并将它们相加 但是当我有负值时

  • 埃拉托色尼筛法 - 实现返回一些非质数值？

    我用 Java 实现了埃拉托斯特尼筛法 通过伪代码 public static void sieveofEratosthenes int n boolean numArray numArray new boolean n for int i

  • 如何高效计算连续数的数字积？

    我正在尝试计算数字序列中每个数字的数字乘积 例如 21 22 23 98 99 将会 2 4 6 72 81 为了降低复杂性 我只会考虑 连续的数字 http simple wikipedia org wiki Consecutive in

随机推荐

  • 何时使用无符号值而不是有符号值？

    什么时候适合使用无符号变量而不是有符号变量 那么在一个for loop 我听到了很多关于这个问题的意见 我想看看是否有任何类似的共识 for unsigned int i 0 i lt someThing length i SomeThin

  • Haskell 中的 IO Int 和类似单元测试

    From 九十九道 Haskell 问题 问题23 从列表中提取给定数量的随机选择的元素 这是部分解决方案 为简单起见 此代码仅从列表中选择一个元素 import System Random randomRIO randItem a gt

  • 如果mysql表不存在则创建

    我不太使用 php mysql 但我需要一个我认为相对简单的任务 检查表是否存在 如果不存在则创建它 我什至无法获得有用的错误消息 并且数据库中没有创建表 显然我的语法有问题

  • 禁用 jqGrid 选定行的子网格扩展

    问题 带有子网格的 jqGrid 我想禁用主网格某些行的展开 折叠功能 我其实找到了一个方法 grid jqGrid setGridParam afterInsertRow function rowid aData rowelem var

  • 如何在对象数组中查询算法数据

    我有一个数据数组 其中 Algolia 索引中包含多个对象 如下所示 status available startDate 2000 10 20 endDate 2022 10 20 availablePlatform 1 2 3 avai

  • 将表标准化为第三范式

    这道题显然是一道家庭作业题 我听不懂我的教授 也不知道他在选举期间说了什么 我需要一步一步地进行说明 首先将下表规范化为 1NF 然后是 2NF 然后是 3NF 我感谢任何帮助和指导 好吧 我希望我都记得正确 让我们开始吧 Rules 让它

  • 如何使用节点谷歌客户端 API 来获取已获取令牌的用户配置文件？

    通过获取用户个人资料信息curl curl i https www googleapis com userinfo v2 me H Authorization Bearer a google account access token 通过获

  • 更改默认 JLabel 字体

    我将如何为所有人设置默认字体JLabel实例 而不是为每个设置字体JLabel独立 Use UIManager定义 JLabel 的默认字体 import java awt FlowLayout import java awt Font i

  • 收益返回和异常处理[重复]

    这个问题在这里已经有答案了 我刚刚遇到一个使用yield return 的方法 但没有抛出我期望的ArgumentException 的情况 我在这里用最简单的类重建了这个案例 class Program static void Main

  • 将十六进制字符（连字）转换为 utf-8 字符

    我有一个从 pdf 文件转换而来的文本内容 文本中有一些不需要的字符 我想将它们转换为 utf 8 字符 例如 人工免疫系统 转换为 Arti 社会免疫系统 像一个字符一样转换 我用了gdex学习ascii角色的价值 但我不知道如何将其替换

  • 如何将WebView设置为非全屏？

    我正在尝试在我的 Android 应用程序中使用 WebView 我正在代码端 而不是 XML 创建我的 webview 我的问题是 当我调用 webview 的 loadUrl 方法时 webview 进入全屏模式 如何保持 webvie

  • 尝试编译此代码是否会导致 IDE 终止或编译器无法运行？

    提防Exit内联函数中的命令用法 我这里一直使用Delphi XE3 Symptom 在某些情况下 当调用包含以下内容的内联函数时Exit命令 以及返回值使用内联函数的directly in WriteLn 编译器报告错误消息 dcc 退出

  • 二进制 XML 文件第 8 行：膨胀类片段时出错，Google 地图

    在此应用程序中 我尝试添加功能性 V2 谷歌地图 我已经查看了大多数关于创建活动 获取地图密钥以及创建 xml 文件的教程 以尝试看看我是否错过了任何步骤 我已经完成了 4 次 但事实并非如此好像我错过了任何一步 Here是我使用的网站 当

  • “SecretKeyFactory 不可用”是什么意思？

    这有什么问题吗 for Object obj java security Security getAlgorithms Cipher System out println obj javax crypto SecretKeyFactory

  • 如何将颜色条位置向右移动

    I draw a scatter chart as below 代码是 sc plt scatter x y marker o s size r c clr vmin lb vmax ub cmap mycm alpha 0 65 cbar

  • 在sql存储过程中传递表名

    是否可以将表名作为输入参数传递给存储过程 例如 create procedure test tablename char 10 as begin select from tablename end go 我知道这行不通 那么 如果我想将表名

  • iOS 实时确定名片的角点

    我想实现像这个应用程序这样的名片检测功能 https scanbot io 相机应检测到名片并自动拍摄它的照片 仅名片 我的想法是使用BradLarson s GPUImage库 检测角点 使用 Harris 角点检测算法 计算获得的角点的

  • 使用 ClosedXML C# 库，在尝试保存时如何找出导致此错误的数据

    我有一个 C 应用程序 可以使用以下命令导出到 Excel封闭XML 它工作正常 但遇到了一个问题 当我点击时 var ms new MemoryStream workbook SaveAs ms 我得到一个例外 hexadecimal v

  • 名为 Tuple 的 C# 可以用作 MVC 页面模型类型吗？

    在 C 7 中 您可以命名元组 var foo Name Joe Age 42 如果我使用以下方法将其传递给 MVC 模型 return View foo 那么cshtml文件中应该使用什么语法来声明模型呢 虽然这不起作用 但类似 mode

  • 有人可以解释一下 Big-Oh 如何与求和一起使用吗？

    我知道这严格来说不是一个编程问题 但它is一个计算机科学问题 所以我希望有人能帮助我 I ve been working on my Algorithms homework and figuring out the Big Oh Big O

热门标签