这个的时间复杂度是多少？它使用了3个循环，最里面的循环依赖于最外面的循环？

Question

function fun(N) {
    
    let k = 0;
    for(let i = N; i >= 1; i = i/2) {
        for (let g = 1; g <= N/i;g = g + 1) {
            for (let h =1; h <= i;h = h + 1) {
                k = k + 1;
            }
        }
    }
    return k;
}

我对给定问题的分析如下：

外层循环一直运行，直到 i 小于 1，并且在每次迭代中，i 除以 2。这意味着外层循环将以相对于 N 为底的 2 对数运行。具体来说，外层循环将一直运行，直到 i 变成小于1，迭代次数可以表示为log2(N)。

中间循环运行N/i次，其中i是外循环的控制变量。因此，中间的循环对时间复杂度贡献了 N 倍。

最内层循环运行 i 次，并且依赖于外层循环。因此我们不考虑它的时间复杂度。

因此，函数的总体时间复杂度为 O(N log N)

Answer 1

您对时间复杂度为

O(N log N)

的答案是正确的，但您的推导不是正确的。

考虑涉及

g

和

h

的内部两个循环。最内层索引为

h

的循环运行

i

次，因此复杂度为

O(i)

。索引为

j

的循环运行

N/i

次，因此具有复杂性

O(N/i)

。由于这两个循环是嵌套的，因此总复杂度为

O(i) * O(N/i) = O(N)

。因此，内部两个循环的时间复杂度与

i

无关，并且始终为

O(N)

。

索引为

i

的最外层循环运行

O(log N)

次，并且您背后的逻辑是正确的。

因此，所有三个循环的总时间复杂度为

O(log N) * O(N)

，给出的答案为

O(N log N)

。