計算機科學基礎/演算法複雜度

演算法複雜度

“演算法是抽象的配方，規定了可能由人類、計算機或其他方式執行的過程。因此，它代表了一個非常通用的概念，有許多應用。”——大衛·哈雷爾，“演算法——計算的精神”。

我們已經瞭解到演算法是問題的概念解決方案。計算演算法可以用計算機可以執行的通用工作單元來描述/定義，這樣它們就與程式語言和執行環境（計算機）無關。演算法編寫是一個創造性的過程，正如弗朗西斯·沙利文所說：“對我來說，偉大的演算法是計算的詩歌。就像詩歌一樣，它們可以是簡短的、含蓄的、密集的，甚至神秘的。但一旦解開，它們就會為計算的某些方面投下新的光彩。”您已經看到了使用虛擬碼和流程圖等抽象符號記錄的示例演算法。

一旦演算法被實現/編碼，即被具體的符號表示，它們就會在體現它們的程式中變得活躍起來。程式可以由計算機執行/執行。能夠執行不同的程式來實現各種演算法是計算機作為機器的獨特功能。通常，當我們購買一臺機器時，例如家用電器，我們假設它具有一組定義明確的功能。例如，微波爐應該加熱和烹飪我們的食物，僅此而已。我們不希望微波爐能夠為我們洗衣服。計算機器（計算機）則不同。我們希望它執行任何程式使其執行的功能——計算機的功能是可擴充套件的。如果我們將計算機比作汽車，程式設計師就是可以使汽車做不同事情的司機（在一定程度上），而使用者就像乘坐汽車享受功能的乘客。這也是每個人都需要學習計算機程式設計的原因，因為它賦予你讓計算機做不同事情的自由。

演算法的正確性

演算法必須正確才能有用。我們必須仔細檢查我們的演算法，以消除錯誤，然後再使用它們建立程式。如果演算法有錯誤，則無法建立正確的程式。我們經常提醒學生，如果他們的演算法在紙上不起作用，它們在計算機上也無法起作用。因此，我們必須首先在紙上找出我們的演算法。

即使演算法的設計是正確的，我們也可能在程式設計過程中引入錯誤。像任何自然語言一樣，程式語言也有自己的語法，包括使用該語言的語法規則。當我們違反這些規則時，就會在程式中引入語法錯誤。這種型別的錯誤很容易修復，事實上，大多數現代程式編輯器可以檢測到此類錯誤並提醒我們。另一種型別的錯誤是邏輯錯誤，這是由於語言使用不當造成的。換句話說，我們語法正確的程式對計算機沒有意義或沒有意義。例如，食譜即使所有句子都語法正確，也可能不清楚或具有誤導性。你可能認為計算機在執行邏輯錯誤的程式時也會出錯。這是真的，但這種情況很少見，尤其是在配備了錯誤檢測機制的現代計算機中。我們通常假設計算機不會出錯。如果程式沒有生成正確的結果，那就是人為錯誤的結果。

我們也稱邏輯錯誤為軟體錯誤。最初的“錯誤”實際上是一個硬體故障——一隻飛蛾卡在機電計算機中。現在，錯誤通常用於指代計算機系統中的任何錯誤/故障，包括硬體和軟體。當計算機程式有錯誤時，它會產生錯誤的結果或崩潰，因為計算機可能不知道下一步該做什麼。另一個更微妙的錯誤可能會導致計算機程式永遠無法完成，被稱為無限迴圈，這顯然不是我們想要的。

錯誤幾乎是不可避免的，因為人類會犯錯誤。那麼，我們如何修復錯誤以確保程式的正確性呢？我們必須測試我們的程式以驗證其正確性。測試包括程式的樣本輸入和程式的預期輸出。我們可以透過對程式進行樣本輸入並收集實際輸出來執行測試。如果實際輸出與預期輸出匹配，則程式透過測試，否則程式或測試中存在錯誤（測試也可能出錯）。我們通常使用一組測試（測試套件）來測試演算法的不同部分。這個過程被稱為除錯，如以下虛擬碼所示

for each test in the test suite
  run and compare the actual output to the desired output
  if they match move on to the next test
  otherwise fix the bug and repeat the whole process

請注意，除了非常簡單的程式外，很難使我們的測試詳盡無遺。當程式變得更大更復雜時，覆蓋所有可能情況所需的測試數量會迅速增加。正如戴克斯特拉所說，“程式測試可以用來證明存在錯誤，但不能用來證明不存在錯誤！”有一些技術可以證明程式的正確性。例如，計算機處理器的微程式碼通常透過形式驗證來證明其正確性。

演算法的“優劣”

通常總有多種方法可以解決同一個問題，因此，也有多種演算法可以使計算機為我們解決問題。除了正確地解決問題外，我們還希望能夠比較/評估解決同一個問題的演算法。我們必須定義演算法設計中“優劣”的標準/度量。這些標準或度量可以包括簡單性、易於實現性、執行速度或答案的精確性。在計算中，我們最關心的是解決方案速度，因為快速的演算法可以在相同的時間內解決更大的問題或更多的問題。這也稱為效率——對許多過程的經濟衡量。通常，許多程式的有用性取決於結果的及時性。例如，一個需要 24 小時才能預測第二天天氣的程式幾乎沒有用。

給定一個演算法，我們如何衡量它的“速度”？一種可能的方法是實現演算法，執行結果程式，並測量其執行時間——程式執行開始和結束之間經過的時間。這種方法存在一些挑戰。首先必須實現演算法，這可能是一項艱鉅的任務。其次，要執行兩個程式來比較它們的執行時間，我們必須對它們進行相同的輸入（也稱為工作負載，例如要排序的百萬個數字列表），並且輸入的大小永遠不理想。第三，執行程式的“速度”受執行環境的影響，例如機器的硬體配置。以食譜為例。不同的廚師肯定需要不同的時間來完成它。需要的食物數量肯定會放大差異——隨著我們增加配料的數量，冗長的食譜需要更長的時間來完成。但是，食譜中有一些內在特性會影響準備時間。如果食譜包含打雞蛋，可以指導廚師將每個雞蛋打碎並單獨攪拌，或者先將所有雞蛋打碎在一起攪拌。顯然，第一種方法由於涉及的步驟更多而更慢。計算中的演算法表現出類似的特徵。回想一下，演算法必須用計算機可以執行的工作單元（步驟）來定義，以便它可以直接在程式語言中實現。演算法中步驟的排序和組織方式會顯著影響實現演算法的程式的執行時間。

由於演算法是解決問題的概念性方案，我們希望在抽象意義上研究它們的“速度”，而無需實際實現它們。這在計算機科學中被稱為演算法分析。在這種方法中，我們採用用虛擬碼或流程圖描述的演算法，計算步驟數量（工作單位），這始終是輸入大小的函式。在上述食譜示例中，遵循第一種方法（分別打破每個雞蛋並將其攪拌）所需的時間與所涉及的雞蛋數量成正比。事實上，如果只需要一個雞蛋，兩種方法之間沒有區別。我們不測量針對特定輸入大小所採取的步驟，而是關注步驟數量和輸入大小之間的關係函式，這顯示了工作量（成本）隨著輸入大小增加而增長的模式。這樣的函式也稱為增長函式。然後，我們應用漸近分析，它將函式比較為輸入接近無窮大，以簡化函式，因為隨著輸入大小接近無窮大，工作單位之間的差異消失（我們可以假設打破雞蛋和攪拌雞蛋所花費的時間相同），並且任務中最“複雜”部分的成本將佔主導地位（重複步驟 10 次的部分將超過只執行一次的任何步驟）總成本。例如，在一個食譜中，我們有一個快速步驟（每份服務 0.0001 秒）重複 10 次，而一個慢速步驟（每份服務 10 秒）不重複，N 份服務量（輸入大小）將花費 $0.0001*10*N$ 在重複步驟上總共花費秒，並且始終在慢速步驟上花費 10 秒。當 N 大於 10000 時，重複部分的成本將超過慢速部分的成本。在漸近分析中，我們可以忽略慢速步驟，因為當 N 接近無窮大時，它對總成本的貢獻可以忽略不計。透過簡化的增長函式，我們可以將它們歸類，並認為每個類別的演算法具有相似的效能特徵。這種分析並不完全精確，但它在研究演算法的性質和預測其效能方面非常有用。我們學習如何將演算法歸類，並根據它們所屬的類別對其效能進行排名。我們使用大 O 符號表示每個類別。

總之，我們討論了以下幾個關於演算法複雜度分析的關鍵概念

演算法是解決問題的概念抽象方案，程式是計算機可以執行的具體可執行程式碼。我們不能在計算機上執行演算法；我們只能執行實現演算法的程式。因此，演算法的效能在定義上是抽象的（不能具體定義或測量）。
演算法的優劣度量必須是演算法本身的內在特徵——反映設計“巧妙性”的東西，而與實現細節和未來的執行環境無關。
從經濟角度來看，我們關心演算法的時間和空間成本。在本課程中，我們將只關注時間成本。我們不能實際測量演算法的時間成本，但我們可以研究時間成本和輸入大小之間的關係，這反映了演算法的內部複雜度（或巧妙性）。我們將這種關係表示為增長函式，其中輸入大小為變數，總成本為值。透過僅保留支配項（漸近分析）可以簡化增長函式，因為當輸入變得非常大（最終接近無窮大）時，其他項無關緊要。簡化的增長函式被歸類，演算法可以根據它們所屬的類別進行排名。
當輸入大小足夠大時，低複雜度類別的演算法將比高複雜度類別的演算法效能更好。我們關心大型輸入大小，因為任何演算法都可以快速解決小問題。使用這種演算法分析技術，我們可以評估和比較演算法，以預測在實際實現任何演算法之前實現這些演算法的程式的相對效能。
效率，作為另一個經常使用的術語，與複雜度成反比。更復雜的演算法效率更低，因為它透過變得更復雜而對計算資源的利用效率更低。

示例

至少有兩種方法可以計算 1 到 N 之間所有數字的總和。以下是兩種演算法

演算法 1：手動逐個新增所有數字
演算法 2：使用此公式計算結果 $(N+1)*(N/2)$

考慮以下問題：如果我們手動執行這兩種演算法，哪一種執行速度更快，如果

N = 2？
N = 100？
N = 1,000,000？

讓我們看看演算法在計算機上的表現（實現後）。以下指令碼使用一個塊來實現演算法 1，該塊迭代遍歷範圍內的所有數字並將它們逐個新增到總和中。

一個 Snap! 指令碼，用於新增兩個數字之間的所有數字。

可以使用演算法 2 解決相同的問題，該演算法使用函式來計算結果，如以下指令碼和報告塊所示。

一個 Snap! 報告塊，用於計算範圍內所有數字的總和並報告結果。

一個 Snap! 塊，用於計算範圍內所有數字的總和。

兩個指令碼（程式）都採用相同的輸入——定義範圍的兩個數字。範圍內的數字數量是輸入大小，或者更確切地說，是問題大小。我們假設工作單位是算術運算 $+-*/$ 、賦值操作和報告操作。這樣的假設是合理的，因為實際上這些操作花費的時間相同，而與運算元無關。如果您執行這些程式並嘗試不同的輸入大小，您將觀察到，隨著您增加輸入大小，第一個程式的執行時間穩步增加，而第二個程式的執行時間沒有變化。我們能預測這種行為嗎？

讓我們將演算法分析應用於這兩個演算法。第一個演算法迴圈遍歷數字以獲取總和，因此成本（步驟數 - 加法）和輸入大小之間的關係函式為 $f=a+b*N$ ，假設 N 是輸入大小，a 和 b 是建立指令碼變數的成本和加法的成本。請注意，a 和 b 都是常數，因為它們對於給定的計算機不會改變。我們可以將函式簡化為 $f=N$ ，因為當 N 接近無窮大時，常數不再重要。我們將具有這種增長函式型別的演算法分配到更精簡的演算法類別，這種函式稱為線性時間，用 $O(N)$ 表示。第二個演算法始終花費相同的時間，因為它執行的運算集與輸入大小無關。它屬於常數時間類別，用 $O(1)$ 表示。

讓我們考慮另一個問題：列表中的數字是否不同？以下是在虛擬碼中描述的直接演算法。

步驟 1：將第一個數字與列表中的所有其他數字進行比較。如果在任何時候看到相同的數字，停止並回答否。
步驟 2：透過從列表中獲取下一個數字並將其與所有其他數字進行比較來重複步驟 1。
步驟 3：使用完列表中的所有數字後，停止並回答是。

輸入大小是列表的大小。列表中的數字越多，回答問題所需的時間就越長。根據演算法，第一個比較可能會發現兩個相同的數字，從而立即回答問題。這是一個好的設計，因為在這一點上，沒有必要繼續執行演算法的其餘部分。當我們分析演算法時，我們專注於最壞情況，因為演算法的效能取決於實際輸入，我們不應該依賴運氣！因此，對於該演算法，成本和輸入大小之間的關係（增長）函式應該是 $f=N*(N-1)$ ，因為在最壞情況下（所有數字都是唯一的），演算法必須將每個數字與列表中的所有其他數字進行比較，然後才能得出答案。為了簡化函式，只保留最大的主導項，我們得到 $f=N^{2}$ ，這將該演算法置於二次類別 $O(N^{2})$ 中。如果您有興趣，可以複製並執行以下指令碼（演算法的實現），以驗證演算法的預測效能特徵。

讓我們看看另一個類別的演算法：列印所有 n 位數字？

For each number in 0, 1, 2, 3, ..., 9 
 use the number for the first digit
 enumerate all n-1 digit numbers
 append each every n-1 digit number to the first digit to form a n digit number

這個例子有點牽強，但它演示了一個新的效能類別，在我們討論加密技術時非常有用。該演算法很複雜，僅僅是因為它必須生成的輸出（所有 n 位數字）數量很多。因此，輸出部分的成本將佔總成本的絕大部分。為了生成所有 n 位數字，我們必須首先生成所有 n-1 位數字。為了生成所有 n-1 位數字，我們必須首先生成所有 n-2 位數字，依此類推。從後向前研究該過程更容易。假設輸出一個數字是工作單位（輸出一個數字所需的時間相同），生成所有一位數字的成本為 10。為了生成所有兩位數字，我們必須輸出 $10*10=10^{2}$ 個數字。對於三位數字，成本為 $10^{3}$ 。您看到模式了嗎？為了生成所有 n 位數字，成本為 $10^{n}$ 。這種型別的演算法比二次演算法快得多，因為輸入大小在指數中。它們屬於指數時間類別，用 $O(2^{N})$ 表示。根（在本例中為 2）並不重要。因為所有指數函式彼此之間的相似性都比二次函式或線性函式更大。

這是一個 YouTube 影片，說明了氣泡排序演算法和快速排序演算法之間的效能差異：https://www.youtube.com/watch?v=aXXWXz5rF64