1
XYZ(a, b, c, m, n){
For p = 1 to m do
For q=p to n do
c[p,q] = a[p,q] + b[p,q];}
我認爲是N + N-1 + N-2 + ... +(N-M + 1)。但我不確定。它是這個還是m * n?下面的僞代碼的時間複雜度是多少?
XYZ(a, b, c, m, n){
For p = 1 to m do
For q=p to n do
c[p,q] = a[p,q] + b[p,q];}
我認爲是N + N-1 + N-2 + ... +(N-M + 1)。但我不確定。它是這個還是m * n?下面的僞代碼的時間複雜度是多少?
讓我們簡化代碼:
For p from 1 to m
For q from p to n
Do something
假設Do something
部分在固定時間內完成的,什麼決定了代碼的時間複雜度是兩個循環。外循環運行m
次,而內循環運行n-p
,p從1變爲m。
如果m >= n
,Do something
部分重複n+(n-1)+...+1 = n*(n+1)/2 = n²/2 + n/2 = O(n²)
次。
否則,如果n > m
,它的重複n+(n-1)+...+(n-m+1) = (n*(n+1) - (n-m)*(n-m+1))/2 = 1/2 * (n² + n - n² + 2*n*m - n - m² + m) = O(2*n*m - m²) = O(n²)
倍。
無論如何,O(n²)
是一個正確的答案,但如果n >> m
,更確切的答案是O(n*m)
。
提示:'1 + 2 + 3 + ... + N =(N + 1)* N/2'在 – 4386427
一個字 - O(m * n個)。 –