此循环语句的运行时间？

Question

我想弄清楚这个循环语句的Big-O运行时间。有人可以帮我吗？

for (i = 1; i < n*n; i=i*2)

它是O(n^2 lg n)？

Answer 1

不，应该是O(logn)。因为log(n^2) = O(logn)。

Answer 2

它的O（LOGN）：

log(n^2) = 2log(n) = O(logn) 

Answer 3

提出这些问题的答案是正确的; “是O(logn)，因为你的迭代增量是多项式（1,4,8,16等），不是线性的。

你可以这样看待它 - 迭代的次数不是线性的，而是多项式，它与迭代量成对数比例。尽管迭代的次数是二次的，但它在循环执行期间是常量，因此可以忽略2*O(logn)中的量词2。