資料結構 - 演算法基礎

---

---

演算法是一個逐步的過程，它定義了一組指令，這些指令以一定的順序執行以獲得所需的輸出。演算法通常獨立於底層語言建立，即一個演算法可以用多種程式語言實現。

從資料結構的角度來看，以下是演算法的一些重要類別：

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

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

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

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

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

演算法的特徵

並非所有過程都可以稱為演算法。演算法應具有以下特徵：

• 明確性 - 演算法應清晰明確。它的每個步驟（或階段）及其輸入/輸出都應清晰，並且必須只有一個含義。

• 輸入 - 演算法應該有 0 個或多個明確定義的輸入。

• 輸出 - 演算法應該有 1 個或多個明確定義的輸出，並且應該與所需的輸出相匹配。

• 有限性 - 演算法必須在有限的步驟後終止。

• 可行性 - 應該使用可用資源可行。

• 獨立性 - 演算法應該有逐步的指示，這些指示應該獨立於任何程式設計程式碼。

如何編寫演算法？

沒有編寫演算法的明確標準。相反，它取決於問題和資源。演算法從未編寫為支援特定的程式設計程式碼。

眾所周知，所有程式語言都共享基本的程式碼結構，例如迴圈（do、for、while）、流程控制（if-else）等。這些通用結構可用於編寫演算法。

我們以逐步的方式編寫演算法，但並非總是如此。演算法編寫是一個過程，並在問題域明確定義後執行。也就是說，我們應該知道我們正在為其設計解決方案的問題域。

示例

讓我們嘗試透過一個示例來學習演算法編寫。

問題 - 設計一個演算法來新增兩個數字並顯示結果。

Step 1 − START
Step 2 − declare three integers a, b & c
Step 3 − define values of a & b
Step 4 − add values of a & b
Step 5 − store output of step 4 to c
Step 6 − print c
Step 7 − STOP

演算法告訴程式設計師如何編寫程式。或者，演算法可以寫成：

Step 1 − START ADD
Step 2 − get values of a & b
Step 3 − c ← a + b
Step 4 − display c
Step 5 − STOP

在演算法的設計和分析中，通常使用第二種方法來描述演算法。它使分析師能夠輕鬆地分析演算法，而忽略所有不需要的定義。他可以觀察正在使用的操作以及流程是如何流動的。

編寫步驟編號是可選的。

我們設計一個演算法來獲得給定問題的解決方案。一個問題可以用多種方式解決。

因此，可以為給定問題推匯出許多解決方案演算法。下一步是分析這些提出的解決方案演算法並實施最合適的解決方案。

演算法分析

演算法的效率可以在兩個不同的階段進行分析，即實現之前和實現之後。它們如下：

• 先驗分析 - 這是演算法的理論分析。透過假設所有其他因素（例如處理器速度）都是恆定的並且對實現沒有影響來衡量演算法的效率。

• 後驗分析 - 這是演算法的經驗分析。所選演算法使用程式語言實現。然後在目標計算機上執行此操作。在此分析中，收集實際統計資料，例如執行時間和所需空間。

我們將學習先驗演算法分析。演算法分析處理所涉及的各種操作的執行或執行時間。操作的執行時間可以定義為每個操作執行的計算機指令數。

演算法複雜度

假設X是一個演算法，n是輸入資料的規模，演算法 X 使用的時間和空間是決定 X 效率的兩個主要因素。

• 時間因素 - 透過計算關鍵操作的數量（例如排序演算法中的比較）來衡量時間。

• 空間因素 - 透過計算演算法所需的最大記憶體空間來衡量空間。

演算法的複雜度f(n)根據n給出演算法的執行時間和/或儲存空間，作為輸入資料的大小。

空間複雜度

演算法的空間複雜度表示演算法在其生命週期中所需的記憶體空間量。演算法所需的空間等於以下兩個元件的總和：

• 一個固定部分，它是儲存某些資料和變數所需的空間，這些資料和變數獨立於問題的規模。例如，使用的簡單變數和常量、程式大小等。

• 一個可變部分，它是變數所需的空間，其大小取決於問題的規模。例如，動態記憶體分配、遞迴棧空間等。

任何演算法 P 的空間複雜度 S(P) 為 S(P) = C + SP(I)，其中 C 是固定部分，S(I) 是演算法的可變部分，它取決於例項特徵 I。以下是一個簡單的示例，試圖解釋該概念：

Algorithm: SUM(A, B)
Step 1 − START
Step 2 − C ← A + B + 10
Step 3 − Stop

這裡我們有三個變數 A、B 和 C 以及一個常量。因此 S(P) = 1 + 3。現在，空間取決於給定變數和常量型別的資料型別，並將相應地乘以。

時間複雜度

演算法的時間複雜度表示演算法執行到完成所需的時間量。時間需求可以定義為數值函式 T(n)，其中 T(n) 可以測量為步驟數，前提是每個步驟消耗恆定時間。

例如，兩個 n 位整數的加法需要n步。因此，總計算時間為 T(n) = c ∗ n，其中 c 是兩個位相加所需的時間。在這裡，我們觀察到 T(n) 隨著輸入規模的增加而線性增長。