時間復雜度一直很迷。。。。 在網上找了看了一些博客，一句話，看不懂。。。。 于是自己去學了一下，總結為下面的。

算法的效率，就是說一個算法的執行時間，它始終還是由我們執行每一行代碼的次數來決定。我們可為每一個算法編寫一個測試程序，然后拿到機器上去跑，但是由于除了算法本生，測試結果還受到很多其他因素的影響，列如cpu的執行速度等不確定因素，而且我們也不可能為了每一個算法去編寫一個測試程序這樣也不現實。

所以后來人們采用事前估算的方法，依據統計學。這種情況下拋開了其他所有的不確定因素，一個算法的效率由一個算法的本生好壞和輸入規模來決定。

例如:

當n很大的時候，兩種算法的差距就大了起來，第一個是2n+2次，第二個始終都是2次。
上面的兩個算法分別可以看做時間復雜度為n和1，下面來解釋為什么是這樣。

時間復雜度

研究算法的復雜度，側重的研究輸入規模很大的情況，在這種情況下我們就可以忽略一個復雜度中的一些小項，也就是執行次數特別大的情況，因為這樣才能判定一個算法的在某種場景下的好與壞，這個時候就需要利用統計學知識。我們接下來通過大量的例子來解釋。通過這幾個例子為后面的算法時間復雜度做鋪墊。

例一

將設A算法要做2n+3次計算，B需要做3n+1次操作，你覺得哪一個更快一點呢。下面來看看統計的結果。

從結果來看最開始算法A1不及B1，當n大于5的時候，執行次數少于B1，到后面完全勝過它，這就是輸入規模的重要性，而且我們看A2、B2發現當輸入規模很大的時候常數項可以完全忽略。
函數的漸進增長: 給定兩個函數，f(n)、g(n)，如果存在一個整數N當n>N的時候，f(n)總是比g(n)大,那么我們說f(n)的漸進增長比g(n)大。
當

例二

算法C為4n+8,算法D為2n^2 + 8

圖上有錯，第二張圖為C1、C2, D1,D2。
從觀察當中可以可以發現，當n很大的時候，相乘的系數，影響也很小了，比如4n+8和n，在圖上都重疊到一塊兒去了，但是對于C1、C2，系數有影響，但是對比C、D算法的時候，可以看出系數并不影響比較?？梢缘贸鼋Y論系數不影響兩個算法之間的比較，因此也可以去掉。

例三

算法E為2n^2+3n+1，算法F為2n^3+3n+1

通過圖中對比E、F兩個算法，可以看到指數對于測試結果影響很大。

例四

算法G為2n^2，算法H為3n+1,算法I為2n^2+3n+1

因此我們可以得出結論: 判斷一個算法的效率的時候，函數中的常數和次要項都可以忽略，而更應改關注最高項的介數。

時間復雜度的計算

用大寫O()來作為時間復雜度的記法，稱為大O記法

那么我們怎么來推導大O階呢。首先我們需要計算出程序執行的次數，再按照下面總結出來的方式來求解，這里的總結均來自前面的例子

• 只有常數項，將常數看做1,得到O(1)
• 對于多項表達式，只保留最高項，且去除與這個項相乘的常數

其實就是這么簡單。。。。，我在網上看到的其他文章語言實在太官方，明明簡單的東西被這些糟老頭子給整復雜了。下面來看幾個計算的例子:

上面的時間復雜度為O(1)

時間復雜度為O(n)

時間復雜度為o(n^2)

上面的例子為對數階。假設程序執行x次退出循環，那么可以得到等式2^x=n,所以當x=log(2底數)n的時候推出循環，執行次數為log(2)n + 1，所以可以得到最終結果為O(logn)

還有一個空間復雜度，空間可以換取時間，時間也可以換取空間，在實際當中往往要在二者之間達到一個平衡

總結

以上是生活随笔為你收集整理的时间复杂度的全部內容，希望文章能夠幫你解決所遇到的問題。

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