使用 Θ 符号分析以下算法的时间成本
Analyze the time cost of the following algorithms using Θ notation
这么多循环,我一直在数最后一个循环运行了多少次。
我也不知道如何简化求和以获得大的 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
}
任何问题都有两个阶段:
- 你猜答案
- 你证明一下
在简单的问题中,第 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 的意思是“上限和下限”。
这么多循环,我一直在数最后一个循环运行了多少次。 我也不知道如何简化求和以获得大的 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
}
任何问题都有两个阶段:
- 你猜答案
- 你证明一下
在简单的问题中,第 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 的意思是“上限和下限”。