勵志

勵志人生知識庫

什麼是p問題

P問題是一類可以在多項式時間內解決的判定問題。

這類問題可以用確定性算法在多項式時間內判定或解出,例如排序問題、最小生成樹問題和單源最短路徑問題。簡單來說,如果一箇問題存在O(n)、O(nk)、O(nlogn)等多項式時間複雜度的解法,那麼它就被歸類爲P問題,其中“P”代表“多項式”(Polynomial)。在計算複雜度理論中,多項式時間指的是問題的計算時間m(n)不大於問題大小n的多項式倍數。