時間複雜性檢查

你會說這個函數的時間複雜度是多少？我認爲它的O（logN），但你能驗證嗎？如果不是，可以使它成爲LogN？我想算的變化量的旋轉陣列上時間複雜性檢查

int findRotationCount(int A[], int sizeOfArray) //O(logN) 
    { 
     int countOfShift = 0, i; 
     for (i = 0; i < sizeOfArray; ++i) 
     { 
      ++countOfShift; 
      if (i+1 == sizeOfArray) 
       break;; 
      if (A[i] > A[i+1]) 
       break; 
     } 
    }

謝謝！

來源

2013-02-11 user1856602

對我來說看起來像O(N)，其中N是你的sizeOfArray值。

來源

2013-02-11 05:57:51

得到它並更改它，謝謝！ – user1856602 2013-02-11 06:11:31

我認爲這是O(n)，其中n=sizeOfArray。這裏的證明：如果滿足下列條件中的至少一個滿足

你的循環可以結束：

i=n =>有n迭代，因此，你的函數的複雜性O(n)。
A[i] > A[i+1] =>數組中存在一個成員，它大於下一個成員。在這裏你必須考慮你的功能的最壞情況。對於這一個，它是一個按遞增順序排序的數組。這意味着你將遍歷從第一個到最後一個成員的數組，並且永遠不會找到滿足的第二個條件。所以，在最壞的情況下，複雜性是O(n)。

因爲你的函數結束時的條件1至少一到兩個得到滿足，我們已經證明了，在這兩種情況下，複雜度爲O (n)，那麼你就可以說，功能的複雜性也是O(n)。請注意，這是最糟糕的情況分析。

來源

2013-02-11 10:35:59 Milos

時間複雜性檢查

回答

相關問題