具有相同变量的 two/three 内部循环的复杂性

Question

我发现我在解决看似非常简单的复杂性问题时想得太多了。在处理此类问题时，我正在寻找一些“方法”。例如（伪代码）：

int func(int arr[], int n)
{
    int i'
    int a1, a2;
    if (n<=1)
        return arr[0];
    a1 = func(arr, n-1);
    a2 = 0;
    for(i=2, i<=n; i*=i)
    {
        j = i
        while(j>=i)
        {
            a2+=arr[j];
            j/=2;
        }
    }
    return a1+a2;
}

i = 1
while(i<n)
{
    j = 1
    while ( j < i^2)
        j++;
    i=i*2
}

对于第二个例子，我知道外循环运行了 logn 次。结果，内部循环运行：1,...,(n/2)^2, n^2。那么总体西格玛应该是多少？

Answer 1

TL;DR:

你的第一段代码运行s 时间 Θ(n log log n).
你的第二段代码运行s 时间 Θ(n²).
我们需要使用各种数学工具来解决这个问题，而且这些不是简单的代码片段来分析。

让我们从第二个例子开始，而不是第一个例子，因为事实证明它要简单得多。这是第二个例子：

i = 1
while(i<n)
{
    j = 1
    while (j < i^2)
        j++;
    i=i*2
}

我在这里假设 i^2 表示 i² 而不是“i xor 2”，但请纠正我如果我弄错了。 :-)

这是一个很棒的地方，可以介绍这个锻炼大 O 的格言运行次：

"When in doubt, work inside out."

也就是说，从最里面的循环开始，计算出它的复杂性，然后用“做 X 工作”形式的东西替换循环。通过重复此过程，您最终会计算出总体运行时间。

在这里，我们最里面的循环是这个：

j = 1;
while (j < i^2)
    j++;

这个循环做了多少工作？嗯，我们计算到 i²，每次迭代做 O(1) 工作，所以这个循环做 Θ(i²) 工作.请注意，我们用 i 而不是 n 来表示运行time，这是有意为之的。此处完成的工作量根据 i 的值从一个迭代到另一个迭代发生变化，我们将尽可能精确。

用“do Θ(i²) work”替换那个循环给我们这个：

i = 1
while(i < n)
{
    do Θ(i^2) work;
    i = i * 2
}

我们的下一个任务是查看这个简化的循环完成了多少工作。首先，让我们看看 i 在这里取什么值。那将是 1, 2, 4, 8, 16, 32, ..., 即 2⁰, 2¹, 2², 2³, 2⁴, 2⁵, ……更一般地，在外循环的 k 次迭代之后，我们有 i = 2^k。因此，循环所做的功为

(2⁰)² + (2¹)² + (2²)²) + (2³)² + (2⁴)² + ... + (2^k_max)²

其中 k_max 是循环运行s 的 k 的最大值。在这里做一点代数，注意

(2⁰)² + (2¹)² + (2²)²) + (2³)² + (2⁴)² + ... + (2^k_max)²

= (2²)⁰ + (2²)¹ + (2²)² + (2²)³ + ...(2²)^k_max

= 4⁰ + 4¹ + ... + 4^k_max

使用几何数列求和的公式，可以简化为

(4^{k_max + 1} - 1) / 3

= Θ(4^k_max)

所以我们现在需要做的就是计算出 k_max 是多少，然后我们就会完成全部工作。为此，请注意，一旦我们超过 n，此循环就会停止运行ning，这意味着我们将在

时停止此循环

n = 2^k_max

lg n = k_max

这意味着我们将有 lg n 次循环迭代（这里，lg n 表示 log₂ n）。将所有这些放在一起，我们完成的工作是

Θ(4^k_max)

= Θ(4^{log₂ n})

= Θ((2²)log₂ n)

= Θ(2^{2 log₂n})

= Θ(2^log₂n²)

= Θ(n²),

所以我们完成的总功是Θ(n²)。请注意，我们并没有通过简单地查看循环并说类似“这个循环运行s 这么多次，这个循环运行s 这么多次，所以我们只是将它们相乘”相反，我们必须对序列和系列进行一些数学运算，然后慢慢地将事物分开才能得出结果。

现在，让我们继续第二个例子：

int func(int arr[], int n)
{
    int i;
    int a1, a2;
    if (n<=1)
        return arr[0];
    a1 = func(arr, n-1);
    a2 = 0;
    for(i=2, i<=n; i*=i)
    {
        j = i
        while(j>=i)
        {
            a2+=arr[j];
            j/=2;
        }
    }
    return a1+a2;
}

现在，让我们把递归部分放在一边，只关注循环。最里面的循环是这个：

j = i;
while (j >= i)
{
    a2 += arr[j];
    j /= 2;
}

这个循环实际上并不难推理。请注意，内部循环的最后一步 (j /= 2;) 将减少 j，因此它小于 i，并且循环永远不会运行第二次。这意味着循环仅完成 O(1) 总工作量。因此，我们可以用“做 O(1) 工作”之类的东西替换这个循环来得到这个：

int func(int arr[], int n)
{
    int i;
    int a1, a2;
    if (n<=1)
        return arr[0];
    a1 = func(arr, n-1);
    a2 = 0;
    for(i=2, i<=n; i*=i)
    {
        do O(1) work;
    }
    return a1+a2;
}

现在让我们关注这个循环：

for(i = 2; i <= n; i *= i)
{
    do O(1) work;
}

我们在这里做了多少工作？ i 取的值将是 2, 4, 16, 256, 65536, ...。我们在这里寻找某种模式，看看我们是否可以算出执行的循环迭代次数。如果我们检查这些值，我们可以看到它们等于 2¹、2²、2⁴, 2⁸, 2¹⁶, 等等。这又可以重写为 2^2⁰, 2^2¹, 2^2², 2^2³, 2^2⁴，等等。换句话说，我们正在看一些双指数的东西，更具体地说，在 k 次迭代之后，i 的值是 2^{2^k}.

一旦我们超过 n，这个循环就会停止，所以我们正在寻找 k 的值，即循环迭代次数，其中 2^{2^k} = n.求解，我们得到

2^{2^k} = n

2k = lg n

k = lg lg n

所以这个循环运行s 进行 lg lg n 次迭代，每次迭代的时间复杂度为 O(1)，所以这里完成的总工作量为 Θ(log log n)。这是有道理的 - 如果您重复计算一个值的平方，you can only do so O(log log n) times before you overshoot the number n.

然后我们可以用类似“do Θ(log log n)”的方法替换循环来得到这个：

int func(int arr[], int n)
{
    if (n <= 1)
        return arr[0];
    
    func(arr, n-1);
    do Θ(log log n) work;
    return /* something */;
}

进步了！我们现在有一个递归函数，它执行 Θ(log log n) 工作，然后在 n 减一时调用自身。将其写成递归关系是下一步值得尝试的好方法。让 T(n) 表示函数在使用参数 n 调用时所做的工作量。然后我们有那个

T(n) = T(n - 1) + log log n

为什么这是我们得到的复发？那么，当输入大小为 n 时完成的工作是 log log n，加上评估 n - 1 上的递归调用所需的工作量。（我在这里删除了 Θ 只是为了使数学更容易。）

我们可以将这种重复迭代几次，看看是否发现了一种模式：

T(n) = T(n - 1) + log log n

= T(n - 2) + log log (n - 1) + log log n

= T(n - 3) + log log (n - 2) + log log (n - 1) + log log n

如果我们想象一直执行到最后，我们会得到类似

的东西

T(n) = log log 2 + log log 3 + log log 4 + ... + log log (n - 1) + log log n

那么这简化为什么呢？好吧，我们可以通过注意到

得到一个很好的保守上限

T(n) = log log 2 + log log 3 + log log 4 + ... + log log (n - 1) + log log n

≤ log log n + log log n + log log n + ... + log log n + log log n

= n log log n

= O(n log log n)

这给出了 O(n log log n) 工作的上限。我们可以为下限做类似的事情：

T(n) = log log n + log log (n-1) + log log (n-2) + ... + log log (3) + log log 2

≥ log log n + log log (n-1) + log log (n-2) + ... + log log (n/2)

≥ log log (n/2) + log log (n/2) + log log (n/2) + ... + log log (n / 2)

= (n / 2) log log (n / 2)

= Ω(n log log n)

所以所做的功是Ω(n log log n)。并且由于它既是 O(n log log n) 又是 Ω(n log log n)，所以它可以 Θ(n log log n) 工作。

如您所见，这里有许多不同的技巧：

由内而外工作以简化循环并计算运行时间。
使用几何级数求和的公式。
使用对数的性质。
为递归函数编写递归关系并迭代递归以获得完成工作的表达式。
上界和下界求和以获得紧界。

我希望我能告诉您有一种“简单”的方法可以始终弄清楚递归函数或循环嵌套需要多少工作，但是唉，它更像是一门艺术而不是一门科学。有许多常见模式，您将通过实践学会识别。

具有相同变量的 two/three 内部循环的复杂性

Complexity in two/three inner loops with same variable

language-agnostic

recursion

complexity-theory

big-o

loops