算法的計算複雜性在大哦，大歐米茄和Theta

Question

我試圖來解決計算複雜度以下問題：

計算下面的算法和 的計算複雜度寫下它的複雜性在大O ，Big Omega and Theta

for i=1 to m { 
    x(i) =0; 
    for j=1 to n { 
     x(i) = x(i) + A(i,j) * b(j) 
    } 
} 

其中A是mxn，b是nx1。

我結束了與大O O(mn^2) 大Omega(1)和Theta(mn^2)。

Answer 1

假設下面的語句在恆定時間用完：

x(i) = x(i) + A(i,j) * b(j) 

這是在這樣對待O（1），並且不依賴於值i和j。既然你遍歷這個說法在內部for循環，正是n時候，你可以說，下面的代碼在運行爲O（n）：

x(i) =0; 
for j=1 to n { 
    meth1 
} 

（假設分配在固定時間內要做的事）。再次，它不取決於i的確切值。最後，我們採取外環考慮：

for i=1 to m { 
    meth2 
} 

方法meth2重複正好m倍，從而緊上限在O（n×m個）時間複雜度。

由於沒有條件語句，也沒有遞歸和數據的結構甲，b和X不改變程序的執行，該算法也大歐米茄（MN）和大西塔（mn）。

當然，你可以高估大哦和低估大歐米茄爲：每算法，你可以說它是Ω（1）以及一些，這是O（2 ^ñ），但重要的是，你不會買那麼多。

Answer 2

回想一下f = Theta(g)當且僅當f=O(g)和f=Omega(g)。

可以在Theta(mn)時間（假設初始實現）和O(m)中的向量之和中計算矩陣向量乘積，因此總運行時間爲Theta(mn)。從這裏開始，時間也是O(mn)和Omega(mn)。