分析代碼片段的複雜度

設A是一個數組[1..n]，其中有零和1，並且函數的複雜度爲theta（m）。對於給定的僞代碼，會是複雜嗎？分析代碼片段的複雜度

counter=0; 
    for(i=0;i<n;i++) 
     { 
      if(a[i]==1) 
      counter++; 
     else 
      func(); 
    }

Accorlding給我的函數func最壞的情況下（）到至多N次被調用時，陣列完全地以零填充會。因此，由於func（）的theta表示爲theta（m）

上述代碼的複雜性爲：theta（mn）.... ???如果不是，請幫助我進行適當的驗證。

來源

2013-10-27 Diljit PR

上述代碼的時間複雜度將爲O（mn）（Big O mn）。
爲什麼？
FUNC（）如你說的是THETA（M）現在計算的時間複雜度時，你注意到自己，最壞情況下，當func被稱爲n次會導致O（MN）。
爲什麼不是Theta（mn）？
Theta對時間複雜性的要求越來越嚴格。這不僅意味着它總是會在最壞的情況下執行，而且最多也會執行mn *（*給出或採用乘法或加法常數）。所以它與投入成比例地增加。但是，我們不能保證Ω（mn）的下界（也就是Ω）。
Go here to find more information on big O vs vs Big Theta

而且你應該能夠回答爲什麼我們不能高估自己的Theta（mn）的下界。

最佳，Digvijay

來源

2013-10-27 07:24:12 digvijay91

請糾正我，如果我錯了，如果f歐米茄（）是（ab）和F大O（）是（AB），然後THETA的F（）是（AB）？？ –

是的，你在本質上是正確的（並且在語言中是錯誤的）。當寫它寫爲f是歐米茄（ab），f是O（ab），而不是像「歐米茄的f」或「f的大O」。 – digvijay91

如果您的問題已得到解答，請考慮標記已解決的問題。 – digvijay91

分析代碼片段的複雜度

回答

相關問題