的三角形化代碼算法複雜

我有一個稀疏m×n矩陣A的三角以下的（局部的）碼（n爲偶數且m = 3N/2-2）：的三角形化代碼算法複雜

y=0; 
for k=1:n 
if(mod(k,2)==0) 
    y=y+1; 
end 
    for j=k+1:n 
     A(k,j)=A(k,j)-tau*U(k,k); 
     if (k<=n-2) 
      for i=n-1:n 
       A(i,j)=A(i,j)-tau*U(i,k); 
      end 
     end 
     for i=n+1:n-2+y 
      A(i,j)=A(i,j)-tau*U(i,k); 
     end    
    end 
end

，我感興趣的是作爲m和n的函數找到它的精確算法複雜度（大O表示法）。由於分支機構，我獲得了不同的結果。

謝謝。

來源

2013-12-14 user3071889

我不確定這是不是主題，但不會[CS.StackExchange]（http://cs.stackexchange.com）是這類問題的適當位置？ – horchler

如何在代碼中使用'm'？ 'y'從0開始？ – pepo

是的，y從0開始，對此感到遺憾。 m不用於代碼中，因爲它的值是n的函數：m = 3n/2-2。 m影響最後一次代碼（因爲在最後一次迭代中n-2 + y = m） – user3071889

y=0; 
// n times 
for k=1:n 
    // some constant complexity stuff 
    // it basically sets y to floor(k/2) 
    if(mod(k,2)==0) 
     y=y+1; 
    end 
    // n-k times 
    for j=k+1:n 
     A(k,j)=A(k,j)-tau*U(k,k); 
     // executed everytime except the last few iteration of the outermost loop 
     if (k<=n-2) 
      // constant complexity 
      for i=n-1:n 
       A(i,j)=A(i,j)-tau*U(i,k); 
      end 
     end 
     // executes y-2 times 
     for i=n+1:n-2+y 
      // so we basically need to bound the number of times this is executed 
      A(i,j)=A(i,j)-tau*U(i,k); 
     end    
    end 
end

在k次迭代環路中間迭代n-k次最後最內層循環迭代其中y-2是（的j不管）

floor(k/2)-2次，最裏面的分配執行Sum (n - k)(k/2 - 2)爲k=1:n倍，這是Θ(n^3)。

來源

2013-12-14 18:38:02 pepo

的三角形化代碼算法複雜

回答

相關問題