我來通俗易懂的來告訴你，演算法時間複雜度究竟是什麼？

首先何為演算法？學計算機的都知道演算法＋資料結構＝程式！除去各種資料型別，物件等資料結構這些承載資料的東西，剩下的包括增刪改查，加減乘除這些操作都屬於演算法！

既然是操作，就像吃飯睡覺，都會有時間長短，我們對應的分鐘，小時這些在演算法上這就叫做時間複雜度！

那麼演算法時間複雜度又怎麼衡量呢？

數學上使用大O表示法來表示時間複雜度！舉例來說下各種複雜度的事例:

1，O(1)，例如你每次下班回家，都是花費一個小時，不會有變化，這就是常數級的時間複雜度！

2，O(n²)，例如你們聚餐一共有N個人，一開始互相不認識，所以你們要互相握手，每個人都要握手n－1次，也就是總的握手次數是n²級別的，這就是平方級別的時間複雜度！

3，O(n)，比如說你開車旅遊，車速勻速50，那麼你開車的距離就是y＝50x！這就是直線型複雜度！

4，O(log2n)，比如你去圖書館找排好順序的書，你會先從中間看一下，在比較頭尾，確定是在那一邊，然後繼續以同樣的方法不斷篩選，最終找到你要的那本書！這就是對數型複雜度！

我們來算下幾種複雜度中n為1024時候的時間，常量型毫無疑問是1024，n²型為1048576次，直線型為1024的倍數，對數型log2n＝10！也就是說對數型的查詢效率只有很小很小的數！

不僅僅是這些簡單的演算法，我們在演算法中常常遇到二分法查詢，二叉樹尋找，紅黑樹，b樹等等都是在查詢效率上有了極大最佳化的資料結構和演算法！

選用不同的演算法，可能會把我們的查詢效率從一個百萬級降低為一個接近常量級的地步！

所以作為演算法工程師，攻堅好演算法效率是必不可少的一環！！

我是謝逅，程式設計演算法是我吃飯的傢伙！

時間複雜度的表示: O(執行次數)

一個有序的元素列表查詢某個元素可以用二分查詢，每次取中間元素進行比較大小，直到相等。因為每次不符合時總會排除一半的元素 ，所以查詢的次數為log2n，那麼時間複雜度為O(log2n)。如果是一個無序的元素列表，查詢從位置0開始，那麼簡單查詢的次數為n，那麼時間複雜度為O(n)。

除此之外快速排序為O(n*log2n)，選擇排序為O(n*n)。

旅行演算法就是n個旅行地點，你可從某個地方出發到餘下某下一個地點，走完所有地點。從最開始時走有n個地點可以選擇，接下來再走就有n-1個地點可以選擇，這樣直到只有一個地點可以選擇。那麼所有你可走的路徑就是一個階乘，選擇複雜度為O( n!)。

關於陣列和連結串列的操作。先說陣列，因為你有了元素的索引，可以隨機訪問，你就能快速找到這個元素，而且所有元素的讀取都是一樣的步驟，所以讀取時間複雜度為O(1)，陣列的插入和刪除的時間複雜度為O(n)，因為要移動元素。連結串列的特性是每個都儲存了下一個元素的地址，只能順序訪問。那麼讀取插入刪除的時間複雜度分別是O(n)、O(1)、O(1)。

簡單理解：演算法時間複雜度就是當變數等於n的時候，演算法需要操作次數的量級。

舉幾個例子：

O(1):執行次數是一個常數，不管變數多大，執行次數是固定的。

O(n)：執行次數為n次，比如有n個數字，尋找裡面最小的數字是多少，那麼就要全部查詢一遍。

O(n²):最簡單的舉例，雙重迴圈

for (i=1; i<=n; i++){

for (j=1; j<=n; j++){

x++;

}

}　

還有氣泡排序，對於n個變數的陣列，位置需要交換n²次　

O(log2n)：分治演算法，從小到大排列了100個數字，你要找其中的一個，先從第50個開始找，比較大小後選擇是找前50個還是後50個，類推。

下面是時候祭出這張圖了！是不是一目瞭然。

如果演算法裡面有兩個迴圈，一個for迴圈時間複雜度是O(n)，還有一個雙重for迴圈時間複雜度是O(n²)，那麼這個演算法整體的時間複雜度O(n+n²)=O(n²)，就是最大的那個。

常見的演算法時間複雜度由小到大依次為：

O(1)<O(log2n)<O(n)<O(nlog2n)<O(n²)<O(n³)<O(2^n)

1）演算法執行的時間可以反映出演算法的效率麼？

有程式設計經驗的朋友經常會發現，對於同樣一個問題，使用不同的演算法實現，每種演算法執行的時間可能是不同的。比如不同的排序演算法，執行時間上就有差異。

但是，我們靠程式執行時間去衡量演算法的優劣可靠麼？同一個程式如果你放到一臺古董機裡跑的話，執行時間必然會更長。所以憑藉程式執行的時間來衡量演算法的優劣勢不準確的。因為計算機的硬體配置和操作環境等客觀因素會影響程式執行的速度，進而反應在程式執行的時間上。

2）怎樣客觀地評價一個演算法優劣呢？

我們假設計算機執行演算法的每一個基本操作所用的時間是固定的，那麼一個演算法有多少執行步驟，乘以每一步驟需要花費的時間，就是程式執行的總時間。對於不同的計算機而言，程式執行總時間的不盡相同的，但同一個演算法程式執行的基本步驟是相同的，因此我們可以透過演算法包含的基本操作個數去衡量演算法的效率，也就是演算法的時間複雜度。

3）演算法時間複雜度的理解

理論上，我們應該度演算法進行詳細具體的分析。但在實踐中，這種做法的價值卻很有限。對於演算法的時間、空間性質，最重要的瞭解他的數量級和趨勢。舉例來說，可以認為3n^2和100n^2屬於同一個數量級，我們認為它們的效率“差不多”，都為n^2級。

演算法的時間複雜度有三種，分別是：

· 最優時間複雜度：演算法完成工作最少需要多少基本操作；

· 最壞時間複雜度：演算法完成工作最多需要多少基本操作；

· 平均時間複雜度：演算法完成工作平均需要多少基本操作。

實際中，我們主要關注的是最壞時間複雜度，因為它是一個保證，表明演算法在這個數量級內是一定能完成的。

下表中列舉了不同基本操作步驟的情況下，時間複雜度的結果：