確定性演算法與非確定性演算法的區別

在程式設計領域，演算法是一組定義明確的、按順序執行特定任務並實現預期輸出的指令。這裡我們說“一組定義明確的指令”，這意味著使用者在某種程度上知道如果這些指令以預期的方式執行，其結果是什麼。

根據對指令結果的瞭解，演算法分為兩種型別：確定性演算法和非確定性演算法。

閱讀本文，瞭解更多關於確定性和非確定性演算法的資訊，以及它們之間有何不同。

什麼是確定性演算法？

確定性演算法是一種演算法，其中每個演算法的結果都是唯一定義的。因此，確定性演算法執行固定數量的步驟，並且總是以相同的結果完成接受或拒絕狀態。目標機器執行相同的指令並給出相同的結果，這並不依賴於指令執行的方式或過程。

確定性演算法可以在多項式時間內解決問題。確定性演算法總是隻有一個結果，即給定的輸入總是產生相同的結果。數學函式是確定性演算法的一個常見示例。

非確定性演算法是一種演算法，其中每個演算法的輸出不是唯一定義的，因此結果可能是隨機的。因此，非確定性演算法有多個結果。

非確定性演算法採用多條執行路徑，因此很難確定機器的下一個狀態。與確定性演算法不同，非確定性演算法無法在多項式時間內解決問題。隨機函式是非確定性演算法的示例。

以下是確定性演算法和非確定性演算法的主要區別：

關鍵	確定性演算法	非確定性演算法
定義	每個演算法的結果都是唯一定義的演算法稱為確定性演算法。換句話說，我們可以說確定性演算法是執行固定數量步驟並始終以相同的結果完成接受或拒絕狀態的演算法。	每個演算法的結果不是唯一定義的，結果可能是隨機的演算法稱為非確定性演算法。
執行	在確定性演算法執行中，目標機器執行相同的指令併產生相同的結果，這並不取決於指令執行的方式或過程。	對於非確定性演算法，允許執行每個操作的機器選擇這些結果中的任何一個，但要遵守稍後定義的確定條件。
型別	根據確定性演算法的執行和結果，它們也被分類為可靠演算法，因為對於特定的輸入指令，機器將始終給出相同的輸出。	非確定性演算法被分類為不可靠演算法，因為對於特定的輸入，機器在不同的執行中會給出不同的輸出。
執行時間	由於結果已知且在不同的執行中一致，因此確定性演算法需要多項式時間來執行。	由於結果未知且在不同的執行中不一致，因此非確定性演算法無法在多項式時間內執行。
執行路徑	在確定性演算法中，演算法的執行路徑在每次執行中都是相同的。	對於非確定性演算法，演算法的執行路徑在每次執行中並不相同，並且可能採用任何隨機路徑來執行。

這兩種演算法之間最顯著的區別在於，確定性演算法每次執行的執行路徑相同，而非確定性演算法在不同的執行中可以採用任何隨機的執行路徑。

Kiran Kumar Panigrahi

更新於：2023年2月21日

20000+ 次瀏覽

完成課程獲得認證