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;
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;
O(n^2),如果我理解正确的话。
为什么需要两个内部循环我不明白。为什么不在同一个循环中对B和C求和呢?
让我们追踪每个循环在每个迭代中执行的次数。
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)
——————
此外,可以查看以下链接:
为初学者详细解释:
最外层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。
最坏情况下时间复杂度为O(n²)。
虽然有三个循环,但并不是全部嵌套在一起,因此导致了O(n²)的时间复杂度。
此外,你可以清楚地看到内部循环不会从1到n(就像外部循环那样)。但是因为这只会将时间复杂度改变一些常数,所以我们可以忽略这一点,并说它只是O(n^2)。
这表明时间复杂度是一个衡量标准:您的算法将随着这个顺序进行“扩展”,而且永远不会花费更长的时间。(然而,更快总是可能的)
要了解有关“计算”任何算法的最坏情况复杂度的更多信息,我可以指向我之前提出的相关问题