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;
sonal
问问题
7907 次
3 回答
8
O(n^2),如果我没看错的话。
为什么你需要两个内部循环超出了我的范围。为什么不在同一个循环中求和 B 和 C?
于 2009-01-09T13:42:38.773 回答
2
只是为初学者详细解释:
最外层的 for 循环将运行 n 次(0 到 n) 然后在最外层的 for 循环中有两个 for 循环。第一个 for 循环将从 1 转到 n (1+2+3+4+.....+n) 第二个 for 循环将从 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。
于 2017-09-22T02:19:02.210 回答
1
最坏的情况是 O(n²)。
确实有三个循环,但不是都在彼此内部,因此给出了 O(n²)。
此外,您可以清楚地看到内部循环不会从 1 变为 n(就像外部循环一样)。但是因为这只会将时间复杂度改变一些常数,所以我们可以忽略它并说它只是 O(n^2)。
这表明时间复杂度是一种衡量标准:您的算法将按此顺序扩展,并且不会再花费更多时间。(但总是可以更快)
有关“计算”任何算法的最坏情况复杂度的更多信息,我可以向您指出我之前提出的一个相关问题
于 2009-01-09T13:52:22.933 回答