使用Θ表示法分析以下算法的时间成本

Question

这么多循环，我一直在计算最后一个循环运行了多少次。我也不知道如何化简求和得到大。谁来帮帮我吧!

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. 你证明给我看

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

---

外循环从n到0，因此迭代次数为O(n)。中间的循环很难分析，因为它的边界取决于i的当前值。就像我们通常在猜测o率时所做的那样，让我们把它的边界替换为从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率。所以我现在必须证明我的猜测是正确的。

---

要证明这一点，请使用"sandwich"技术-以两种不同的方式编辑程序，一种使其运行时更小，另一种使其运行时更大。如果您设法使两个新程序具有相同的o率，您将证明原始代码具有相同的o率。

这里有一个"smaller"或";faster"代码:

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次迭代。

这里有一个"更大"的";或";slower"代码:

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²)

---

这里我使用0，它应该是Θ。O通常被定义为"上限"，有时根据上下文表示"上限"或"下限"。在我的回答中，0意味着"上限和下限"。