运行具有三个嵌套 for 循环的函数时间的渐近增长

Question

我有一个函数的伪代码（如下）。
我知道如果 i、j 和 k 中的每一个都是 1那么最坏的情况运行时间将是 O(n^3)。我正在努力理解 n/2 对运行时间的影响（如果有的话）。任何指导都会很棒。

for i=n/2; i < n; increase i by 1
    for j=1; j < n/2; increase j by 1
        for k = 1; k < n; increase k by k*2
            Execute a Statement

Answer 1

你的理解不正确

k增加k*2导致对数时间，复杂度实际上是O(n^2 * log n)

O(n/2) = O(n)，因此n/2对渐近增长没有任何影响。

如果不确定，一般的做法是尽可能精确地统计，然后去掉常量。

for i 将执行 n/2 次，for j 也会执行 n/2 次，k 将执行 log n 次。

n/2 * n/2 * log n = (n^2/4) * log n。您可以删除常量，因此 O(n^2 * log)

Answer 2

最坏情况时间复杂度不是O(N^3)

检查最里面的for循环。 K 增加 K * 2 这意味着，最里面的 for 循环将花费 O(lgN) 时间

另外两个外层循环各需要O(N)次，N/2不会对运行次的渐近增长产生任何影响。

因此，整体时间复杂度为 O(N^2 * lgN)

Asymptotic Growth of Run Time of function with three nested for loops