Java 資料結構 - 演算法分析

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

演算法分析

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

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

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

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

演算法複雜度

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

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

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

演算法f(n)的複雜度給出了演算法的執行時間和/或儲存空間，以n（作為輸入資料的規模）表示。

空間複雜度

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

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

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

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

演算法：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)隨著輸入規模的增加而線性增長。