这两个嵌套循环的时间复杂度是多少

Question

给出：

public void iterate(int n){
    int i =n;
    while (i > 0){
        for (int j = 0; j < n; j++) {
            System.out.println("*");
            i = i/2;
        }
    }
}

我可能会认为此操作的时间复杂度是线性的，因为比较

i > 0

将是恒定的，并且内部的 for 循环将是线性的。因此总共

linear time.

但在我看来，我仍然认为操作是二次的。

任何人都可以给我一个关于嵌套循环的复杂性的更清晰的解释吗？谢谢

Answer 1

正如所写，这里的外循环实际上并没有做任何事情，因为

i

在内循环内递减到 0。 while 循环只会执行一次。 for 循环体将执行

n

次，因此算法为 O(n)。

如果将

i = i/2;

移至 for 循环体的 after 运行，则 while 循环将执行 log(n) 次，因此算法将是 O(n * log(n))。

Answer 2

算法的总成本是O(n)。

更具体地说，for 循环有 n 次迭代，每次迭代需要恒定的时间。 （顺便说一句，在这 n 次迭代的 log n 次之后，i 将达到 0。对于剩余的 n - log n 次迭代，i 继续等于 0。打印语句在这 n 次迭代的每次迭代中执行。） ，for循环的总成本是O(n)。在这 n 次迭代结束时，i 为 0，因此 while 循环在第一次迭代后退出。