本文首發(fā)公眾號：架構(gòu)精進，請移步，排版比較清晰。
經(jīng)常有同學(xué)在 LeetCode 的題解中問解法的復(fù)雜度是多少。作為一個懶人，我一直在「逃避」這個問題，畢竟這東西聽起來就這么「復(fù)雜」。
但本著對題解認(rèn)真負(fù)責(zé)的態(tài)度（心虛），我想趁此機會做一個總結(jié)。下面我將通過一些較為經(jīng)典的算法題聊一聊幾種常見的時間復(fù)雜度。
什么是時間復(fù)雜度？算法的時間復(fù)雜度（Time complexity）是一個函數(shù)，用于定性描述算法的運行時間。
提出時間復(fù)雜度的目的是：分析與比較完成同一個任務(wù)而設(shè)計的不同算法。
大 O 符號時間復(fù)雜度通常用 大 O 符號（Big O notation）表示。大 O 符號 又被稱為漸近符號，是用于描述函數(shù) 漸近行為。
舉個例子，假設(shè)我們解決一個規(guī)模為 n 的問題要花費的時間為 T(n)T(n)：
T(n)=4n2?2n+2T(n)=4n2?2n+2
當(dāng) n 不斷增大時，n2n2 開始占據(jù)主導(dǎo)地位，而其他各項可以被忽略，寫作 T(n)=O(n2)T(n)=O(n2)。因此時間復(fù)雜度可被稱為是 漸近 的。
常見復(fù)雜度比較但由于復(fù)雜度始終是 O(9×9)O(9×9)，加上使用哈希表來判斷元素是否存在，所以算法的復(fù)雜度始為 O(1)O(1)。
對數(shù)時間若 T(n)=O(logn)T(n)=O(logn)，則稱其具有對數(shù)時間。
常見例子：
二叉樹相關(guān)操作二分查找為什么是 logn？什么是對數(shù)？首先，我們復(fù)習(xí)一下 對數(shù)。
對數(shù) 是冪運算的逆運算。假如 x=βyx=βy，那么就有 y=logβxy=logβx。其中：
ββ 是對數(shù)的底（基底）yy 就是 xx（對于底數(shù) ββ）的對數(shù)那我們說一個算法的復(fù)雜度是 O(logn)O(logn)，那么 lognlogn 這個對數(shù)的底數(shù)去哪了？
換底公式二分查找如果一個算法的時間復(fù)雜度為 O(n)O(n)，則稱這個算法具有線性時間。隨著樣本數(shù)量的增加，復(fù)雜度也隨之線性增加。常表現(xiàn)為單層循環(huán)。
來看一到例題 求眾數(shù)。這里我們用了摩爾投票法，時間復(fù)雜度為 O(n)O(n)。
若算法復(fù)雜度為 T(n)=O(nlogn)T(n)=O(nlogn)，則稱這個算法具有線性對數(shù)時間?？梢岳斫鉃閳?zhí)行了 n 次對數(shù)時間復(fù)雜度的操作。
有幾種排序算法的平均時間復(fù)雜度都是線性對數(shù)時間，例如：
堆排序：前 K 個高頻元素快速排序：顏色分類歸并排序二次時間若算法復(fù)雜度為 T(n)=O(n2)T(n)=O(n2)，則稱這個算法具有二次時間，即時間復(fù)雜度隨著樣本數(shù)量的增加呈平方數(shù)增長。常表現(xiàn)為雙層循環(huán)。
常見的算法中有一寫比較慢的排序算法，例如：
冒泡排序選擇排序插入排序由于涉及的排序算法很多，若一一講解的話就偏離這篇文章的側(cè)重點了。如果大家對各類算法感興趣可以參考：維基百科：排序算法。
算法是生活中的大智慧，而我們都是智慧的受益者。
1.《時間復(fù)雜度計算的例題 從經(jīng)典算法題看時間復(fù)雜度》援引自互聯(lián)網(wǎng)，旨在傳遞更多網(wǎng)絡(luò)信息知識，僅代表作者本人觀點，與本網(wǎng)站無關(guān)，侵刪請聯(lián)系頁腳下方聯(lián)系方式。
2.《時間復(fù)雜度計算的例題 從經(jīng)典算法題看時間復(fù)雜度》僅供讀者參考，本網(wǎng)站未對該內(nèi)容進行證實，對其原創(chuàng)性、真實性、完整性、及時性不作任何保證。
3.文章轉(zhuǎn)載時請保留本站內(nèi)容來源地址，http://f99ss.com/keji/347050.html