算法的大O表示法

Question

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

以下声明的Big O表示法是什么: -

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

Answer 1

一旦我以指数方式增长,它就是O(log(n)).

如果n大16倍,预计循环次数只会比它多两次.

对于大O表示法并不重要.它增长为4 ^ i = n.在这种情况下,2和4只是常量 (4认同)
塞缪尔是对的.迭代次数是这个问题的答案"为了超过n,必须多少次2乘以4？" 答案是(加或减1,因为你正在进行大O计算时草率很糟糕!)天花板(n/2的日志基数4),所以复杂性是log-O的大O( n)/ log(4) - 1/2,即O(log(n)). (4认同)

Answer 2

尝试计算n的几个(小)值的循环次数,然后绘制结果图(水平轴上的n,垂直轴上的循环计数).当你第一次学习时,解决问题是很好的.

根据您为n选择的值,您可能看不到该模式.例如,对于n = 10和n = 20,循环计数是相同的.考虑到循环计数何时发生变化,也会发现一种可以告诉你大O时序的模式.

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