最好、最壞同平均情況複雜度

最好、最壞同平均情況複雜度係分析演算法嘅複雜度嗰陣成日會講到嘅三個指標：

• 最好情況（best case，$\Omega$）：指段演算法喺「最好」（最慳時間空間）嘅情況下消耗幾多時間空間資源；
• 最壞情況（worst case，$O$）：指段演算法喺「最壞」（最嘥時間空間）嘅情況下消耗幾多時間空間資源；
• 平均情況（average case）：指段演算法喺「平均」嘅情況下要消耗幾多時間空間資源，即係攞嗮所有可能情況，計佢哋平均要消耗幾多時間空間資源。

概論

睇埋：運算複雜度

舉例說明，用線性搜尋（linear search）演算法做例子：試諗家陣要指定一個 input 數，再由一條 input 陣列度搵個數出嚟，如果陣列入面冇嗰個數，就顯示（例如）「搵唔到」，即係

• Input：
  1. 要摷嗰條陣列，同埋
  2. 想搵嗰個數；
• Output：
  • 想要嗰個數喺陣列嘅第幾個位（好似下圖噉由 0 數起），
  • 如果陣列入面冇嗰個數，就出「搵唔到」噉嘅字。

要解呢條問題，線性搜尋係最簡單直接嗰種做法－即係將條陣列入面啲數逐個逐個攞嚟睇，搵到就畀嗰個數出嚟做 output，睇完嗮成條陣列都冇就畀「搵唔到」做 output。如果用線性搜尋解決條問題嘅話：

• 喺最好情況下，陣列入面有想要嗰個數，而且個數咁啱得咁橋喺正條陣列第一格，所以電腦行 1 步就行完，用符號表達係 $\Omega (1)$；
• 喺最壞情況下，陣列入面有想要嗰個數，但個數咁啱得咁橋喺正條陣列最尾嗰格，所以電腦行 n 步至行完（n = 條陣列嘅長度），用大 O 符號表達係 $O(n)$；
• 簡化講，平均情況複雜度（$A$）就要噉計：

  $A=\sum _{i=1}^{n}{\frac {\theta (i)}{(n+1)}}$，當中 $\theta (i)$ 係指「input 大細 $=i$ 嗰陣，要行幾多步」；

－喺廿一世紀初嘅應用上，最壞情況複雜度一般畀人視為重要資訊，分析演算法嗰時實會睇；相比之下，啲人比較少會留意平均同最好情況複雜度。

睇埋

• 運算複雜度理論