卡住上估計的時間複雜

時間複雜性爲O（n * m）的估計卡住上估計的時間複雜

for i ← 0 to n do 
    for j ← 0 to m do 
    STATEMENT1; 
    end for 
end for

所以，關於這個算法

for i ← 0 to n do 
    for j ← 0 to l do 
    STATEMENT1; 
    end for 
    for k ← 0 to m-l do 
    STATEMENT2; 
    end for 
end for

因爲用於處理語句1和語句2時間要求是不同的。如果我們定義處理STATEMENT1 = O（1）的時間和處理STATEMENT2的時間= Q（1）我們可以估計該算法的時間複雜度爲n [O [1] + Q [ml]]或者O（n l）+ Q（n（m-1））

請幫助檢查我的解決方案或任何人都可以幫助使解決方案更簡單！

來源

2016-03-25 ThienLuan

怎麼樣** **你估計的時間複雜度，並解釋爲什麼你認爲是這樣嗎？然後，我們可以提供有關爲什麼它不是您想法的建議，或者確認您已經正確使用它。正如現在寫的，你要求我們爲你完成你的任務，而且我很確定你的導師希望看到**你的**工作，而不是我們的工作。 –

謝謝@KenWhite，我已經編輯了內容再次討論！ – ThienLuan

這是O(n * l + n * (m - l)) = O(n * m)

我認爲$ L<米$。否則，它會減少到你的第一個問題。

來源

2016-03-25 02:05:51

我知道應該簡化時間複雜性，但是如果處理STATEMENT1和STATEMENT 2的時間要求不同。你的解決方案是否仍然正確？ – ThienLuan

@ThienLuan你可以相應地修改它。假設'STATEMENT1'需要'T1'時間，'STATEMENT2'需要'T2'時間，那麼它是'O（n * l * T1 + n *（m-1）* T2）'，但是如果它們的複雜性是獨立的'n，m，l'，這仍然是正確的。 –

謝謝亨利！這是一個很好的解決方案！ – ThienLuan

讓我們考慮STATEMENT1需要（常量）的時間來執行，同樣STATEMENT2需要k2（常量）的時間來執行。

現在，讓我們做一些數學：

語句1：

將被執行的時間STATEMENT1總數，n.l。因此，它花費的總時間= n.l.k1。

語句2：將執行

次STATEMENT2總數，n.(m-l)。因此它花費的總時間=
n.(m-l).k2。

現在，由算法所花費的總時間將是：

=> n.l.k1 + n.(m-l).k2 
=> n.(l.k1 + (m-l).k2) 
=> n.(l.k1 + m.k2 - l.k2) 
=> n.(m.k2 + l.(k1 - k2)) 

Now separate these two equations out and apply big_O notation onto them 

=> n.m.k2  +   n.l.(k1 - k2) (Apply Big O notation) 
    since k2 is    since k1-k2 is 
    constant     constant 

=> O(n.m) + O(n.l) -eq(i)

時間分割當量（ⅰ）成3案件如下：

CASE 1：m >>> l
然後(n.m)將接管(n.l)
而且，最後的等式將變成O(n.m)

案例2：l >>> m
然後(n.l)將接管(n.m)
而且，最終的公式將變得O(n.l)。

案例3：l ≈ m

=> O(n.m) + O(n.l) 
=> O(n.m) + O(n.m) Since l ≈ m 
=> 2.O(n.m)   Since we are dealing with Big O thus we can eliminate a prefix 2 
=> O(n.m)

來源

2016-03-25 05:30:04 surajsn

卡住上估計的時間複雜

回答

相關問題