使用 Θ 符号分析以下算法的时间成本

Question

这么多循环，我一直在数最后一个循环运行了多少次。我也不知道如何简化求和以获得大的 Theta。请有人帮助我！

    int fun(int n) {
        int sum = 0
        for (int i = n; i > 0; i--) {
                for (int j = i; j < n; j *= 2) {
                        for (int k = 0; k < j; k++) {
                                sum += 1
                        }
                }
        }
        return sum
    }

Answer 1

任何问题都有两个阶段：

你猜答案
你证明一下

在简单的问题中，第 1 步很简单，然后您可以跳过第 2 步或将其解释为“显而易见”。这个问题有点棘手，所以这两个步骤都需要一些更正式的思考。如果你猜错了，你会卡在你的证明中。

外层循环从n到0，所以迭代次数为O(n)。中间循环很难分析，因为它的边界取决于 i 的当前值。就像我们通常在猜测 O-rates 时所做的那样，让我们将其范围替换为从 1 到 n。

    for (int i = n; i > 0; i--) {
            for (int j = 1; j < n; j *= 2) {
                perform j steps
            }
    }

这个新的中间循环，包括内循环在内的运行-时间是1+2+4+...+n，或者说大约是2*n，也就是O(n)。与外循环一起，你得到 O(n²)。这是我的猜测。

我编辑了代码，所以我可能更改了 O-rate。所以我现在必须证明我的猜测是正确的。

为了证明这一点，请使用“三明治”技术 - 以两种不同的方式编辑程序，一种使其运行时间更小，另一种使其运行时间更长。如果你设法使两个新程序具有相同的 O-rate，你将证明原始代码具有相同的 O-rate。

这是一个“更小”或“更快”的代码：

    do n/2 iterations; set i=n/2 for each of them {
            do just one iteration, where you set j = i {
                perform j steps
            }
    }

这段代码速度更快，因为每个循环做的工作更少。它执行类似 n²/4 次迭代的操作。

这是一个“更好”或“更慢”的代码：

    do n iterations; set i=n for each of them {
            for (int j = 1; j <= 2 * n; j *= 2) {
                perform j steps
            }
    }

我为中间循环设置了上限 2n 以确保它的最后一次迭代是 j=n 或更大。

这段代码比较慢，因为每个循环做了更多的工作。中间循环（及其下的所有内容）的迭代次数为 1+2+4+...+n+2n，类似于 4n。所以整个程序的迭代次数大约是 4n²。

我们以一种比较正式的方式得到了：

n²/4 ≤ runtime ≤ 4n²

所以运行时间 = O(n²)。

这里我用O，应该是Θ。 O通常被定义为“上限”，而有时它意味着“上限或下限，取决于上下文”。在我的回答中，O 的意思是“上限和下限”。

使用 Θ 符号分析以下算法的时间成本

Analyze the time cost of the following algorithms using Θ notation

algorithm

for-loop

big-o