c++ - 算法的大 O 表示法

Question

我无法解决问题；有人能帮我吗？

以下语句的大 O 符号是什么：-

for (int i=2;i<=n;i=i*4)
    sum++;

score 12 · Accepted Answer

一旦 i 呈指数增长，它就是 O(log(n))。

如果 n 大 16 倍，则预计循环只运行两次。

score 5 · Accepted Answer

尝试计算 n 的几个（小）值的循环数，然后绘制结果（水平轴上的 n，垂直轴上的循环数）。当你第一次学习时，解决一个问题是很棒的。

根据您为 n 选择的值，您可能看不到该模式。例如，对于 n=10 和 n=20，循环计数是相同的。考虑循环计数何时会改变也会揭示一种模式，它可以告诉你大 O 时间。

一旦你对算法时序有了更好的理解，你就不需要经历这个有点耗时的过程。您将能够通过代码分析以代数方式计算出大 O 时序。

score 4 · Accepted Answer

我认为大 O 表示法的方式是完成需要多长时间，这就是复杂性。例如，如果您有一个冒泡排序，当您对要排序的项目进行排序时，大约需要 n*n 次操作才能完成，即 O(N^2)。

对于二分查找，随着 n 大小的增加，您需要进行 log2(n) 操作来查找该值。由于操作数是以 log 为单位的，因此二进制搜索的 O(log N)（其中 log 是 2 的 log）。

对于你所拥有的，随着它以线性方式增加，即 O(N)，你有 N 次操作（即使你偏移）。这是线性搜索的符号，因为它可能需要 n/2 个选项的平均值才能找到一个值，它仍然是 O(N)。

我会在 O(N) notation 上查看维基百科。它有更多的技术解释，以及更多的大 O 符号信息。

score 3 · Accepted Answer

一旦你知道起点和乘数i> 1，它们的确切值在 big-O 项中没有任何区别（它们只转换为添加到核心组件或乘以核心组件的O(log N)常数，并且在 big-O 推理中会忽略这些常数——毕竟这是大 O 推理的核心点！！！）。

score 1 · Accepted Answer

由于您将其作为家庭作业练习，因此您真正需要做的是回到首要原则；即O符号的数学定义。算出随着“n”的增加有多少个简单的计算步骤，用代数方式算出极限，然后继续回答。

在实践中，大多数人根据对经典示例的了解和经验来估计“O”复杂度。而且他们经常弄错。

score 0 · Accepted Answer

假设“sum++”是常数，这是一个非常合理的假设，算法为 O(log ₄ n)。

因为循环从 2 到 n，所以你知道它最多为 O(n)。但是，由于您的增量在每个循环中都乘以 4，因此在循环中花费的时间呈指数级减少。

score 0 · Accepted Answer

i 的前 4 个值是 2、8、32、128，因此显示循环将经历多少次迭代的公式是：

(((对数(n)/对数(2))/2)+0.5

7 回答 7