Q

僞算法

2014-01-20 62 views 1 likes

1

當學習算法和數據結構我在一個問題都有所涉獵，考試多項式分析是什麼意思，如果一個算法有僞多項式時間效率（分析）僞算法

做了很多的搜索，但轉身空手

2014-01-20 TheGuyWithStreetCred

A

回答

2

這意味着該算法是關於輸入大小的多項式，但輸入實際上指數增長。

例如取子集和問題。我們有一組S的n整數，我們想找到一個總和爲t的子集。

要解決這個問題，你可以檢查每個子集的總和，所以它是O（P）其中P是子集的數量。然而實際上子集的數量是2^n，所以該算法具有指數複雜度。

我希望這篇介紹有助於理解維基百科的文章http://en.wikipedia.org/wiki/Pseudo-polynomial_time :)

2014-01-20 21:55:20

相關問題