2018-03-15 14:20:08

偽多項式時間：如果一個算法的傳統時間復雜度是多項式時間的，而標準時間復雜度不是多項式時間的，則我們稱這個算法是偽多項式時間的。

想要理解“偽多項式時間”，我們需要先給出“多項式時間”的一個清楚的定義。

對于“多項式時間”，我們的直觀概念是時間復雜度,其中是一常數。比如，選擇排序的時間復雜度是，是多項式時間；暴力解決TSP問題的時間復雜度是，不是多項式時間。我們稱這種時間復雜度為“傳統時間復雜度”。

我們通常認為傳統時間復雜度中的變量表示數據的輸入規模。比如，選擇排序中，指待排序數組中元素的個數；TSP問題中表示圖中節點的數量。但是，這些所謂的輸入規模，僅僅是直觀的定義，并不足夠嚴謹。為了標準化這些，在計算標準時間復雜度時，我們給出了輸入規模的標準定義： 一個問題的輸入規模是保存輸入數據所需要的bit位數。 了解了輸入規模的定義，我們來看“多項式時間”的標準定義： 對于一個問題，在輸入規模為x的情況下，如果一個算法能夠在O()時間內解決此問題，則我們稱此算法是多項式時間的，其中為一常數。 排序問題：用選擇排序對元素個數為的數組進行排序時，傳統時間復雜度為。輸入規模，因此，得到的標準時間復雜度是，仍然是多項式時間。因為這的n是只輸入數據的數目。 素數測試：給定數字 n，通過從 2 到根號 n 的整數遍歷，判斷 n 是否為素數。看似時間復雜度是O(n)，但是這里的n是輸入數字的大小，真實的輸入規模為 x = logn，因此實際的時間復雜度是O(x ^ 2)，是指數級的時間復雜度。這就是個偽多項式時間復雜度。

轉載于:https://www.cnblogs.com/hyserendipity/p/8573472.html

總結

以上是生活随笔為你收集整理的伪多项式时间 Pseudo-polynomial time的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。