什么是時間復雜度？

時間復雜度并不是表示一個程序解決問題需要花多少時間，而是當程序所處理的問題規模擴大后，程序需要的時間長度對應增長得有多快。也就是說，對于某一個程序，其處理某一個特定數據的效率不能衡量該程序的好壞，而應該看當這個數據的規模變大到數百倍后，程序運行時間是否還是一樣，或者也跟著慢了數百倍，或者變慢了數萬倍。

不管數據有多大，程序處理所花的時間始終是那么多的，我們就說這個程序很好，具有 $O(1)$ 的時間復雜度，也稱常數級復雜度；數據規模變得有多大，花的時間也跟著變得有多長，比如找n個數中的最大值這個程序的時間復雜度就是 $O(n)$，為線性級復雜度，而像冒泡排序、插入排序等，數據擴大2倍，時間變慢4倍的，時間復雜度是 $O(n^2)$，為平方級復雜度。還有一些窮舉類的算法，所需時間長度成幾何階數上漲，這就是 $O(a^n)$ 的指數級復雜度，甚至 $O(n!)$ 的階乘級復雜度。

不會存在 $O(2?n^2)$ 的復雜度，因為前面的那個"2"是系數，根本不會影響到整個程序的時間增長。同樣地，$O(n^3+n^2)$ 的復雜度也就是 $O(n^3)$的復雜度。因此，我們會說，一個 $O(0.01?n^3)$的程序的效率比 $O(100?n^2)$ 的效率低，盡管在n很小的時候，前者優于后者，但后者時間隨數據規模增長得慢，最終 $O(n^3)$ 的復雜度將遠遠超過 $O(n^2)$。我們也說，$O(n^{100})$ 的復雜度小于 $O(1.01^n)$ 的復雜度。

容易看出，前面的幾類復雜度被分為兩種級別，其中后者的復雜度無論如何都遠遠大于前者。像 $O(1)$, $O(\ln (n))$, $O(n^a)$等，我們把它叫做多項式級復雜度，因為它的規模n出現在底數的位置；另一種像是 $O(a^n)$ 和 $O(n!)$ 等，它是非多項式級的復雜度，其復雜度計算機往往不能承受。當我們在解決一個問題時，我們選擇的算法通常都需要是多項式級的復雜度，非多項式級的復雜度需要的時間太多，往往會超時，除非是數據規模非常小。

總結

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

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