資料結構與算法之美 複雜度分析(下)

• ​​前言​​
• ​​最好、最壞情況時間複雜度​​
• ​​平均情況時間複雜度​​
• ​​均攤時間複雜度​​

文章是觀看王争老師的資料結構與算法之美所寫

前言

本文将會講解以下内容

• 最好情況時間複雜度
• 最壞情況時間複雜度
• 平均情況時間複雜度
• 均攤時間複雜度

最好、最壞情況時間複雜度

// n表示數組array的長度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
       pos = i;
       break;
    }
  }
  return pos;
}      

我們先來看看上面這個代碼的時間複雜度

• 如果情況好的話，我們可能第一個元素就找到了，就不需要周遊剩餘元素，時間複雜度就是O(1)
• 如果情況很糟糕的話，可能找不到此元素，我們需要周遊數組所有元素，時間複雜度為O(n)。

• 在不同的情況下，這段代碼的時間複雜度是不一樣的。

  為了表示代碼在不同情況下的不同時間複雜度，我們需要引入三個概念：最好情況時間複雜度、最壞情況時間複雜度和平均情況時間複雜度。

平均情況時間複雜度

要查找的變量 x 在數組中的位置，有 n+1 種情況：在數組的 0～n-1 位置中和不在數組中。我們把每種情況下，查找需要周遊的元素個數累加起來，然後再除以 n+1，就可以得到需要周遊的元素個數的平均值，即：