演算法分析

在演算法的理論分析中，通常以漸近意義估計其複雜度，即估計任意大的輸入的複雜度函式。 “演算法分析”這一術語由唐納德·克努特提出。

演算法分析是計算複雜度理論中的重要組成部分，它為解決特定計算問題所需的演算法資源提供了理論估計。大多數演算法的設計都是為了處理任意長度的輸入。演算法分析是確定執行演算法所需的時間和空間資源量。

通常，演算法的效率或執行時間表示為一個函式，該函式將輸入長度與步數（稱為時間複雜度）或記憶體容量（稱為空間複雜度）相關聯。

分析的必要性

本章將討論演算法分析的必要性以及如何為特定問題選擇更好的演算法，因為一個計算問題可以用不同的演算法來解決。

透過考慮特定問題的演算法，我們可以開始發展模式識別能力，以便藉助該演算法解決類似型別的問題。

演算法之間通常大相徑庭，儘管這些演算法的目標相同。例如，我們知道可以使用不同的演算法對一組數字進行排序。對於相同的輸入，一種演算法執行的比較次數可能與其他演算法不同。因此，這些演算法的時間複雜度可能會有所不同。同時，我們需要計算每種演算法所需的記憶體空間。

演算法分析是對演算法解決問題的能力進行分析的過程，包括所需時間和空間（實現時儲存所需的記憶體大小）。然而，演算法分析的主要關注點是所需時間或效能。通常，我們執行以下型別的分析：

• 最壞情況 - 對大小為a的任何例項所採取的最大步數。

• 最好情況 - 對大小為a的任何例項所採取的最小步數。

• 平均情況 - 對大小為a的任何例項所採取的平均步數。

• 均攤 - 應用於大小為a的輸入的一系列操作隨時間的平均值。

為了解決問題，我們需要考慮時間和空間複雜度，因為程式可能在一個記憶體有限但空間充足的系統上執行，或者反之亦然。 在這種情況下，如果我們比較氣泡排序和歸併排序。氣泡排序不需要額外的記憶體，但歸併排序需要額外的空間。儘管氣泡排序的時間複雜度高於歸併排序，但如果程式需要在記憶體非常有限的環境中執行，我們可能需要應用氣泡排序。

增長率

增長率定義為當輸入大小增加時演算法執行時間增加的速率。

增長率可分為兩種型別：線性型和指數型。如果演算法隨著輸入大小的增加而線性增加，則為線性增長率。如果演算法的執行時間隨著輸入大小的增加而呈指數增加，則為指數增長率。

證明演算法的正確性

一旦設計出解決問題的演算法，就非常重要的一點是該演算法必須始終為給定的每個輸入返回期望的輸出。因此，需要證明所設計的演算法的正確性。這可以使用多種方法完成：

反例證明

確定演算法可能不正確的案例並應用。如果反例適用於該演算法，則證明了其正確性。否則，必須設計另一個解決此反例的演算法。

歸納證明

使用數學歸納法，我們可以透過證明演算法對於基本情況輸入（例如1）是正確的，並假設它對於另一個輸入k是正確的，然後證明它對於k+1也是正確的，從而證明演算法對於所有輸入都是正確的。

迴圈不變式證明

找到一個迴圈不變式k，證明基本情況對於演算法中的迴圈不變式成立。然後應用數學歸納法來證明演算法的其餘部分是正確的。