1. 首頁 > 生活經驗 > >

多項式時間在決定型機器上是最小的復雜度類別 什么叫多項式時間算法

經驗分享生活經驗


多項式時間是決定性機器中復雜度最小的類別 ， 當機器模型發生變化時仍然很強 ， 也可以在副程式組合過程中保持封閉 。
數學家有時認為比多項式時間長的算法是一種快速計算 ， 對應于超多項式時間 ， 這意味著只要任何多項式時間的輸入量足夠大 ， 超多項式時間所需的解決問題的時間最終將大大超過任何多項式時間 。
指數時間就是一例 。
定義：
在計算復雜性理論中 ， 多項式時間是指一個問題的計算時間不大于問題大小的多項式倍數 。任何抽象機器都有一個復雜性類 ， 包括可以在多項式時間內解決的問題 。
多項式時間是決定性機器中復雜度最小的類別 ， 當機器模型發生變化時仍然很強 ， 也可以在副程式組合過程中保持封閉 。
【多項式時間在決定型機器上是最小的復雜度類別 什么叫多項式時間算法】強多項時間是指根據輸入數據的結構復雜性 ， 這個問題的運算時間不會因輸入數據的數量而變化 。