算法

Question

的時間複雜度，我此刻的學習算法，並寫了下面的代碼，如果在一個維數組存在一個峯值，其發現。我的問題是我如何知道它的最佳情況或平均情況的時間複雜度？

最壞情況下的時間複雜度（如果數組元素被排序）是O（n），但是如果數組沒有排序並且它有10個元素，代碼會運行5個循環來獲得結果，的數組大小，所以任何人都可以告訴我如何用算法表示法來編寫它。

int[] arr = { 1,5,2,7,8,9,4,6,7}; 
int peak; 

int count = 0; 
for (int i = 1; i < arr.Length - 1; i++) 
{ 
      peak = -1; 
      if (arr[i - 1] <= arr[i] && arr[i] >= arr[i + 1]) 
      { 
       peak = arr[i]; 
       i++; 
      } 
      else if (arr[i - 1] >= arr[i] && i - 1 == 0) 
      { 
       peak = arr[i - 1]; 
      } 
      else if (arr[i + 1] >= arr[i] && i + 1 == arr.Length - 1) 
      { 
       peak = arr[i + 1]; 
      } 

      if (peak != -1) 
       listBox1.Items.Add(peak.ToString()); 

      count++; 
} 

listBox1.Items.Add(count.ToString()); 

Answer 1

你仍然把它寫成O(n)因爲大O是最壞的情況下（在這裏是線性時間。）在這種情況下n當然是數組的長度。理論上你的循環內沒有任何東西超過O(1)（我將忽略列表附加並將其稱爲常量）。

在注意到您對n/2迭代的意見後。 n/2是等於說(1/2)n或O((1/2)n)，因爲我們做的與大O邊界時忽略所有係數這相當於O(n)。