以下代码的时间复杂度是多少？ O(nlogn) 还是 O(N)？什么时候复杂度为O(nlogn)？

Question

我在计算这段代码的时间复杂度时有点困惑。将不胜感激。

N=4
index=1
sum=0
while index < N:
    j = N
    while j >= index:
        j =j//4
        sum+=10
    index+=1

Answer 1

从分析内循环开始。由于在一次迭代中 j = j//4，并且 j 从 N 变为 <=index，对于给定的索引，内部循环将花费 ceil(log((N+1)/index)) 时间。
index 从 1 变为 N。
使用 1 和 2，总计 time = ceil(log(N/1)) + ceil(log(N/2)) + ceil(log(N/3)) ... ceil(log(N/N))。
让我们为 N/index 中的索引选择一个随机值。当 index 在 [1, N/4) 范围内时，我们得到 ceil(log(N/index)) = 1。当 index 在 [N/4, N/16) 范围内时，我们得到 ceil(log(N/index)) = 2.
概括地说，当索引在 [N/4^x, N/4^(x-1)) 范围内时，ceil(log(N/index)) = x 的值。此范围内的数字计数为 N/4^(x-1) - N/4^x = 3N/(4^x).
x 从 1 变为 log(N)，因此我们的总和成为 3N * (x/4^x) 对所有 x 的总和。由于 3N 是常数，我们需要在所有 x.

x/4^x

正如@trincot 所指出的，总和有一个常数上限。所以我们得到 O(3N * constant) = O(3N) = O(N).

所以整体时间复杂度是O(N)。

Answer 2

复杂度为O()。

我们看到：

当索引 > /4 时，只有 1 次内部迭代：这发生在大多数外部迭代中：大约 (3/4) 的外部迭代。

否则，当索引>/16时，有2次内迭代。

...等等

我们可以写成下面的和：

(3/4) + 2(3/4²) + 3(3/4³) + ...

然后我们可以提取3个系数：

3[ 1/4 + 2/4² + 3/4³ + ... ]

剩下的是 Wikipedia - low order polylogarithms 中所列形式的幂级数：

∑_{_k=1..∞} = / (1 − )²

...其中 = 1/4，因此该级数收敛于一个常数值。实际上，这个级数的项数是有限的，但是这个无限项已经给了我们一个常数上限。

剩下 3 显然是线性的。

因此复杂度为O()

插图

为了说明这种复杂性，请观察以下脚本如何输出内部循环主体执行总次数之间的比率...它收敛于一个常数：

function test(n) {
    let count = 0;
    for (let index = 1; index < n; index++) {
        for (let j = n; j >= index; j >>= 2) {
            count++;
        }
    }
    return count;
}

for (let n = 1; n < 1e7; n*=2) {
    console.log(test(n) / n);
}

这当然不是证明，而是对上述结论的说明。

以下代码的时间复杂度是多少？ O(nlogn) 还是 O(N)？什么时候复杂度为O(nlogn)？

What will be the time complexity of the following code? O(nlogn) or O(N)? When is the complexity O(nlogn)?

python

algorithm

big-o

time-complexity

插图