algorithm - 这个 for 循环语句的运行时间？

Question

我试图找出这个循环语句的 Big-O 运行时间。有人可以帮帮我吗？

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

是O(n^2 lg n)吗？

score 2 · Accepted Answer

2

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

于 2013-02-03T00:43:48.547 回答

score 2 · Accepted Answer

2

它的 O(logn) ：

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

于 2013-02-03T00:48:24.900 回答

score 1 · Accepted Answer

提出的答案是正确的；ìt 是O(logn)，因为您的迭代增量是多项式（1、4、8、16 等），而不是线性的。

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

3 回答 3