Java 資料結構與演算法

---

---

演算法概念

演算法是一步一步的過程，它定義了一組指令，這些指令以一定的順序執行以獲得所需的輸出。在資料結構方面，演算法的類別如下。

• 搜尋 - 在資料結構中搜索專案的演算法。

• 排序 - 以特定順序對專案進行排序的演算法

• 插入 - 在資料結構中插入專案的演算法

• 更新 - 更新資料結構中現有專案的演算法

• 刪除 - 從資料結構中刪除現有專案的演算法

演算法分析

演算法分析處理資料結構各種操作的執行時間或執行時間。操作的執行時間可以定義為每個操作執行的計算機指令的數量。由於任何操作的確切執行時間因計算機而異，因此我們通常將任何操作的執行時間分析為 n 的某個函式，其中 n 是資料結構中該操作處理的專案數量。

漸進分析

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

漸進符號

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

• Ο 符號

• Ω 符號

• θ 符號

大O符號，Ο

Ο(n) 是表示演算法執行時間上界的正式方法。它衡量最壞情況下的時間複雜度或演算法可能完成所需的最長時間。例如，對於函式f(n)

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

大O符號用於簡化函式。例如，我們可以用Ο(f(nlogn))替換特定的函式方程 7nlogn + n - 1。考慮以下情況

7nlogn +n - 1 ≤ 7nlogn + n

7nlogn +n - 1 ≤ 7nlogn + nlogn

對於 n ≥ 2 使得 logn ≥ 1

7nlogn +n - 1 ≤ 8nlogn

它表明f(n) = 7nlogn + n - 1 在O(nlogn) 輸出範圍內，使用常數 c = 8 和 n₀ = 2。

歐米茄符號，Ω

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

例如，對於函式f(n)

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

西塔符號，θ

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

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