使用C語言的資料結構 - 演算法

演算法

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

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

• 排序 - 用於按特定順序排序專案的演算法

• 插入 - 用於將專案插入資料結構的演算法

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

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

演算法分析

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

漸近分析

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

漸近記號

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

• Ο 符號

• Ω 符號

• θ 符號

大O符號，Ο

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

例如，對於函式 f(n)

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

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

歐米茄符號，Ω

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

例如，對於函式 f(n)

西塔符號，θ

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