查找以下代码的 运行 时间
Finding running time of the following code
public static int loop(int n){
int j = 1;
int n2 = n;
for (int i = 0; i < n; i++) {
n2 *= 5.0/7.0;
for (int k = 0; k < n2; k++) {
System.out.println("Hello.");
}
}
return j;
}
大家好，我在计算上述代码的时间复杂度时遇到了一些困难。
这是我目前的情况：
当i=0时，执行内循环：(5/7) * n
当i=1时，执行内循环：(5/7)^2 * n
...
当i=n时，执行内循环：(5/7)^(n+1) * n
将它们加起来，我得到 O(n * (5/7)^n)。这个分析准确吗？
您的结论不正确；事实上，当 0 < r < 1 时，公式 n * rn 收敛到 0，因为 n 趋于无穷大，所以它绝对不是 运行 时间的上限一个做超过 0 件事的算法。
在你的算法中，r = 5/7，但为了便于阅读，我会在这个答案中继续写 r。对这些项求和的公式给出的结果类似于 n * r * (rn+1 - 1)/(r - 1)。 r 的额外因子是因为序列不是从 1 * n 开始的。简化这个公式需要注意，因为对于0 < r < 1，分数的分子和分母都是负数，分子中的主导项是1，它主导了r n+1 因为n趋于无穷时后者收敛于0.
如果我们将其重写为 n * r * (1 - rn+1)/(1 - r) 就更清楚了。舍弃 r 和 1/(1-r) 的常数因子，我们得到 O(n * (1 - rn+1))，然后舍弃主导项 -rn+1 我们得到 O(n * 1)，或者只是 O(n)。
另一种理解方式是，该序列的上界为 n * (r + r2 + r3 + 。 ..)，其中无限级数收敛于常数 r/(1 - r)，因此它的上界为常数的 n 倍。
public static int loop(int n){
int j = 1;
int n2 = n;
for (int i = 0; i < n; i++) {
n2 *= 5.0/7.0;
for (int k = 0; k < n2; k++) {
System.out.println("Hello.");
}
}
return j;
}
大家好，我在计算上述代码的时间复杂度时遇到了一些困难。
这是我目前的情况：
当i=0时，执行内循环：(5/7) * n
当i=1时，执行内循环：(5/7)^2 * n
...
当i=n时，执行内循环：(5/7)^(n+1) * n
将它们加起来，我得到 O(n * (5/7)^n)。这个分析准确吗？
您的结论不正确；事实上，当 0 < r < 1 时，公式 n * rn 收敛到 0，因为 n 趋于无穷大，所以它绝对不是 运行 时间的上限一个做超过 0 件事的算法。
在你的算法中，r = 5/7，但为了便于阅读，我会在这个答案中继续写 r。对这些项求和的公式给出的结果类似于 n * r * (rn+1 - 1)/(r - 1)。 r 的额外因子是因为序列不是从 1 * n 开始的。简化这个公式需要注意，因为对于0 < r < 1，分数的分子和分母都是负数，分子中的主导项是1，它主导了r n+1 因为n趋于无穷时后者收敛于0.
如果我们将其重写为 n * r * (1 - rn+1)/(1 - r) 就更清楚了。舍弃 r 和 1/(1-r) 的常数因子，我们得到 O(n * (1 - rn+1))，然后舍弃主导项 -rn+1 我们得到 O(n * 1)，或者只是 O(n)。
另一种理解方式是，该序列的上界为 n * (r + r2 + r3 + 。 ..)，其中无限级数收敛于常数 r/(1 - r)，因此它的上界为常数的 n 倍。