資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究計算理論 (TOC) 中的 P 類和 NP 類是什麼？
首先，讓我們瞭解計算理論 (TOC) 中的 P 類。
P 類
P 類包含那些可以在多項式時間內解決的問題，即這些問題可以在最壞情況下以 O(nk) 的時間解決，其中 k 是常數。
這類問題稱為易處理問題，其他問題稱為難處理問題或超多項式問題。
通常，如果存在一個多項式 p(n)，使得演算法可以在 O(p(n)) 的時間內解決任何大小為 n 的例項，則該演算法是多項式時間演算法。
需要 Ω(n50) 時間才能解決的問題對於較大的 n 本質上是難處理的。大多數已知的多項式時間演算法在 O(nk) 時間內執行，其中 k 的值相當低。
多項式時間演算法的優勢在於，所有合理的確定性單處理器計算模型最多都可以以多項式慢速模擬彼此。
NP 類
NP 類包含那些可以在多項式時間內驗證的問題。NP 是一類判定問題，藉助少量額外資訊，很容易檢查給定答案的正確性。因此，我們不是要求尋找解決方案的方法，而只是要求驗證解決方案確實是正確的。
該類中的每個問題都可以使用窮舉搜尋在指數時間內解決。
示例
考慮一個示例，以檢查問題屬於 P 類還是 NP 類
步驟 1 - 如果一個問題屬於 P 類，則意味著我們可以在多項式時間內找到該型別問題的解決方案。
步驟 2 - 如果一個問題屬於 NP 類，則意味著我們可以在多項式時間內驗證可能的解決方案。
步驟 3 - 考慮另一種方法，NP 表示非確定性多項式。具體來說，這意味著如果您能夠構建一臺能夠同時嘗試問題所有可能解決方案的機器，它可以在多項式時間內完成。
我們知道這是正確的，因為我們知道我們可以在多項式時間內驗證可能的解決方案，而該機器基本上是在同時嘗試驗證（測試）問題的潛在答案。
步驟 4 - 因此，如果您可以在多項式時間內解決問題，您當然可以在多項式時間內驗證答案的正確性，不是嗎？當然，如果您能夠證明您的演算法是正確的，並且它可以在多項式時間內找到答案，那麼它必須屬於 P 類。
18K+ 次瀏覽
