time-complexity - 奇怪循环的时间复杂度

Question

这个循环的时间复杂度是多少？

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

   { //Something with O(1) complexity here }

我猜是 O(log n*n)。

标签： time-complexitycomputer-science

Answer 1

你是对的，因为i在每次迭代中加倍，并且循环在i >= n ²时终止，使其运行O(log n ² )迭代。

但是，请注意O(log n ² ) = O(2 log n) = O(log n)。

编辑：但是，正如 Zilog80 指出的那样，这段代码初始化i为0，这将导致循环从0 * 2 = 0开始无限运行。但是，如果您将其初始化为某个正数（常数），那么您的计算是正确的。