tft每日頭條

 > 知識

 > 什麼叫多項式時間算法

什麼叫多項式時間算法

知識 更新时间:2024-07-22 10:08:19

  多項式時間在決定型機器上是最小的複雜度類别,且在機器模型改變時依舊強韌,且也是可在副程式組合過程中保持封閉的類别。

  數學家有時把“比多項式時間長的算法”視為快速計算,相對應的是超多項式時間,表示任何多項式時間的輸入數目隻要夠大,超多項式時間所需的解題時間終究會大大超過任何多項式時間的問題。

  指數時間就是一例。

  定義:

  多項式時間在計算複雜度理論中,指的是一個問題的計算時間不大于問題大小的多項式倍數。任何抽象機器都擁有一複雜度類,此類包括可于此機器以多項式時間求解的問題。

  多項式時間在決定型機器上是最小的複雜度類别,且在機器模型改變時依舊強韌,且也是可在副程式組合過程中保持封閉的類别。

  強多項式時間指的是此問題的運算時間不因輸入資料的數字大小而變動,而是依照輸入資料的結構複雜度。

更多精彩资讯请关注tft每日頭條,我们将持续为您更新最新资讯!

查看全部

相关知識资讯推荐

热门知識资讯推荐

网友关注

Copyright 2023-2024 - www.tftnews.com All Rights Reserved