performance - 嵌套for循环运行时间计算

Question

如何计算此循环的最坏情况运行时间？

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

{
     //do something
}

Answer 1

因为i = 0，i*=2将仍然= 0，这将永远持续下去n > 0

Answer 2

让我们建立起来——

第一的：

for (int i = 1; i < n; i *= 2) --> log(n)

然后：

for (int i = 1; i * i < n; i ++) --> sqrt(n)

所以，看起来你的循环会影响 log(sqrt(n))

Answer 3

形式上，您可以使用 Sigma 表示法进行如下操作：