procedure matrixvector(n:integer);
var i,j:integer;
begin
for i<-1 to n do begin
B[i] = 0;
C[i] = 0;
for j<-1 to i do
B[i]<- B[i]+ A[i,j];
for j<-n down to i+1 do
C[i]<-C[i] + A[i,j]
end
end;
这个算法的最坏时间复杂度是什么？
5
- sonal
3
我觉得自己眼花了。当我第一次阅读时，它没有格式化。当页面刷新后，它变成了漂亮的格式，并在我的面前出现了Jon Skeet的图片。 - duffymo
我认为格式在这里是关键的一部分。第一次我没有看到它是两个循环嵌套在另一个循环中，以为有三个嵌套的循环。 - PolyThinker
我不明白为什么你要问“最坏情况”时间复杂度，因为这里没有情况——它总是执行相同的操作。 - ShreevatsaR
4个回答
9
O(n^2)，如果我理解正确的话。
为什么需要两个内部循环我不明白。为什么不在同一个循环中对B和C求和呢？
- duffymo
5
为什么要在同一个循环中对它们求和？ - ShreevatsaR
为什么不这样做呢？DRY原则表示您将少一个循环。像这样拥有单独的总和有什么优势吗？n *（n + n）= 2n ^ 2表示两个循环; n * n = n ^ 2表示一个循环。Big-O省略常数，但您的墙钟不会。 - duffymo
2但内部循环的大小并不是n，它们相加得到n，所以这应该与合并循环时具有大致相同的运行时间。实际上，可能会更快，因为如果循环被合并，您需要根据循环索引的值（如果j < i则为B，否则为C）进行切换。 - Autoplectic
是的，正如Autopletic所说的那样。无论您是将它们“组合”还是分开，您都会执行相同的加法操作，并且循环运行相同的次数——尝试在同一个循环中同时执行两者只会使代码变得混乱，需要使用“如果j<=i，则将A[i,j]添加到B[i]，否则将其添加到C[i]”这个测试条件。 - ShreevatsaR
1我的挂钟显示使用两个内部循环比一个更快，这正是您从代码中期望的。 - ShreevatsaR
4
让我们追踪每个循环在每个迭代中执行的次数。
procedure matrixvector(n : integer);
var i, j : integer;
begin
for i<-1 to n do begin // OuterLoop
B[i] = 0;
C[i] = 0;
for j <- 1 to i do // InnerLoop_1
B[i] <- B[i] + A[i, j];
for j <- n down to (i + 1) do // InnerLoop_2
C[i] <- C[i] + A[i, j]
end
end;
InnerLoop_1
在OuterLoop的第一次迭代（i = 1）中，InnerLoop_1只执行一次。
在OuterLoop的第二次迭代（i = 2）中，InnerLoop_1执行两次。
在OuterLoop的第三次迭代（i = 3）中，InnerLoop_1执行三次。
. . .
在OuterLoop的最后一次迭代（i = n）中，InnerLoop_1执行n次。
因此，此代码的总执行次数为
1 + 2 + 3 + … + n
= (n(n + 1) / 2) (自然数和公式)
= (((n^2) + n) / 2)
= O(n^2)
InnerLoop_2
在OuterLoop的第一次迭代（i = 1）中，InnerLoop_2执行n - 1次。
在OuterLoop的第二次迭代（i = 2）中，InnerLoop_2执行n - 2次。
在OuterLoop的第三次迭代（i = 3）中，InnerLoop_2执行n - 3次。
. . .
在OuterLoop的第次迭代（i = n - 2）中，InnerLoop_2执行2次。
在OuterLoop的第次迭代（i = n - 1）中，InnerLoop_2执行1次。
在OuterLoop的最后一次（第n次）迭代（i = n）中，InnerLoop_2不执行任何次数。
因此，此代码的总执行次数为
n - 1 + n - 2 + n - 3 + … + 2 + 1 + 0
= 0 + 1 + 2 + … + n - 3 + n - 2 + n - 1
= (n - 1)((n - 1) + 1) / 2 (自然数和公式)
= (n - 1)(n) / 2
= (((n^2) - n) / 2)
时间复杂度
InnerLoop_1 执行次数: (((n^2) + n) / 2)
InnerLoop_2 执行次数: (((n^2) - n) / 2)
相加得：
(((n^2) + n) / 2) + (((n^2) - n) / 2)
= ((((n^2) + n) + ((n^2) - n)) / 2)
= (((n^2) + n + (n^2) - n) / 2)
= (((n^2) + (n^2)) / 2)
= ((2(n^2)) / 2)
= (n^2)
= O(n^2)
——————
此外，可以查看以下链接：
- Deepthi Tabitha Bennet
3
为初学者详细解释：
最外层for循环将运行n次（0到n） 然后有两个循环嵌套在最外层的for循环中。 第一个循环将从1到n（1+2+3+4+.....+n） 第二个循环将从n到1（n+n-1+n-2+....+1）
（1+2+3+4+5+....+n）求和公式是n(n+1)/2
因此，总运行时间可以计算为n + n(n+1)/2 + n(n+1)/2
观察这个方程中的最高多项式，它是n^2。
我们可以进一步简化这个方程，去掉常数并忽略线性部分，这将给我们一个运行时间为n^2。
- john
2
最坏情况下时间复杂度为O(n²)。
虽然有三个循环，但并不是全部嵌套在一起，因此导致了O(n²)的时间复杂度。
此外，你可以清楚地看到内部循环不会从1到n（就像外部循环那样）。但是因为这只会将时间复杂度改变一些常数，所以我们可以忽略这一点，并说它只是O(n^2)。
这表明时间复杂度是一个衡量标准：您的算法将随着这个顺序进行“扩展”，而且永远不会花费更长的时间。（然而，更快总是可能的）
要了解有关“计算”任何算法的最坏情况复杂度的更多信息，我可以指向我之前提出的相关问题
- Sven
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接