Java 資料結構 - 漸進符號

演算法的漸進分析是指定義其執行時效能的數學邊界/框架。使用漸進分析，我們可以很好地得出演算法的最佳情況、平均情況和最壞情況。

漸進分析是輸入約束的，即如果演算法沒有輸入，則認為它在恆定時間內工作。除了“輸入”之外，所有其他因素都被認為是恆定的。

漸進分析是指用計算的數學單位計算任何操作的執行時間。例如，一個操作的執行時間計算為 f(n)，另一個操作的執行時間計算為 g(n²)。這意味著第一個操作的執行時間將隨著 n 的增加而線性增加，而第二個操作的執行時間將隨著 n 的增加而呈指數增加。同樣，如果 n 非常小，則兩個操作的執行時間幾乎相同。

通常，演算法所需的時間分為三種類型：

• 最佳情況 - 程式執行所需的最小時間。

• 平均情況 - 程式執行所需的平均時間。

• 最壞情況 - 程式執行所需的最多時間。

漸進符號

以下是常用的漸進符號，用於計算演算法的執行時間複雜度。

• Ο 符號

• Ω 符號

• θ 符號

大O符號，Ο

符號 Ο(n) 是表示演算法執行時間上界的正式方法。它衡量最壞情況時間複雜度或演算法完成所需的最長時間。

例如，對於函式 f(n)

Ο(f(n)) = { g(n) : 存在 c > 0 和 n0 使得對於所有 n > n0，f(n) ≤ c.g(n)。}

歐米茄符號，Ω

符號 Ω(n) 是表示演算法執行時間下界的正式方法。它衡量最佳情況時間複雜度或演算法完成所需的最短時間。

例如，對於函式 f(n)

Ω(f(n)) ≥ { g(n) : 存在 c > 0 和 n0 使得對於所有 n > n0，g(n) ≤ c.f(n)。}

西塔符號，θ

符號 θ(n) 是表示演算法執行時間上下界的正式方法。它表示如下：

θ(f(n)) = { g(n) 當且僅當 g(n) = Ο(f(n)) 且 g(n) = Ω(f(n)) 對於所有 n > n0。}

常見的漸進符號

以下是一些常見的漸進符號列表：