算法（Algorithm）是指用來操作數(shù)據(jù)、解決程序問題的一組方法帜乞。算法是大廠、外企面試的必備項(xiàng)筐眷，也是每個(gè)高級程序員的必備技能黎烈。針對同一問題，可以有很多種算法來解決匀谣，但不同的算法在效率和占用存儲空間上的區(qū)別可能會(huì)很大照棋。
那么，通過什么指標(biāo)來衡量算法的優(yōu)劣呢振定？其中必怜，上面提到的效率可以用算法的時(shí)間復(fù)雜度來描述，而所占用的存儲空間可以用算法的空間復(fù)雜度來描述后频。
- 時(shí)間復(fù)雜度：用于評估執(zhí)行程序所消耗的時(shí)間梳庆，可以估算出程序?qū)μ幚砥鞯氖褂贸潭取?/li>
- 空間復(fù)雜度：用于評估執(zhí)行程序所占用的內(nèi)存空間，可以估算出程序?qū)τ?jì)算機(jī)內(nèi)存的使用程度卑惜。
在實(shí)踐中或面試中膏执，我們不僅要能夠?qū)懗鼍唧w的算法來，還要了解算法的時(shí)間復(fù)雜度和空間復(fù)雜度露久，這樣才能夠評估出算法的優(yōu)劣更米。當(dāng)時(shí)間復(fù)雜度和空間復(fù)雜度無法同時(shí)滿足時(shí)，還需要從中選取一個(gè)平衡點(diǎn)毫痕。
一個(gè)算法通常存在最好征峦、平均、最壞三種情況消请，我們一般關(guān)注的是最壞情況栏笆。最壞情況是算法運(yùn)行時(shí)間的上界，對于某些算法來說臊泰，最壞情況出現(xiàn)的比較頻繁蛉加，也意味著平均情況和最壞情況一樣差。
通常，時(shí)間復(fù)雜度要比空間復(fù)雜度更容易出問題针饥，更多研究的是時(shí)間復(fù)雜度厂抽，面試中如果沒有特殊說明，講的也是時(shí)間復(fù)雜度丁眼。
時(shí)間復(fù)雜度
要獲得算法的時(shí)間復(fù)雜度筷凤，最直觀的想法是把算法程序運(yùn)行一遍，自然可以獲得户盯。但實(shí)踐中往往受限于測試環(huán)境嵌施、數(shù)據(jù)規(guī)模等因素饲化，直接測試算法要么難以實(shí)現(xiàn)莽鸭，要么誤差較大，而且理論上也沒必要對每個(gè)算法都進(jìn)行一遍測試吃靠，只需要找到一種評估指標(biāo)硫眨，獲得算法執(zhí)行所消耗時(shí)間的基本趨勢即可。
時(shí)間頻度
通常巢块，一個(gè)算法所花費(fèi)的時(shí)間與代碼語句執(zhí)行的次數(shù)成正比礁阁，算法執(zhí)行語句越多，消耗的時(shí)間也就越多族奢。我們把一個(gè)算法中的語句執(zhí)行次數(shù)稱為時(shí)間頻度姥闭，記作T(n)。
漸進(jìn)時(shí)間復(fù)雜度
在時(shí)間頻度T(n)中越走，n代表著問題的規(guī)模棚品，當(dāng)n不斷變化時(shí)，T(n)也會(huì)不斷地隨之變化廊敌。那么铜跑，如果我們想知道T(n)隨著n變化時(shí)會(huì)呈現(xiàn)出什么樣的規(guī)律，那么就需要引入時(shí)間復(fù)雜度的概念骡澈。
一般情況下锅纺，算法基本操作的重復(fù)執(zhí)行次數(shù)為問題規(guī)模n的某個(gè)函數(shù)，也就是用時(shí)間頻度T(n)表示肋殴。如果存在某個(gè)函數(shù)f(n)囤锉，使得當(dāng)n趨于無窮大時(shí)，T(n)/f(n)的極限值是不為零的常數(shù)护锤，那么f(n)是T(n)的同數(shù)量級函數(shù)官地，記作T(n)=O(f(n))，稱O(f(n))為算法的漸進(jìn)時(shí)間復(fù)雜度蔽豺，簡稱為時(shí)間復(fù)雜度区丑。
漸進(jìn)時(shí)間復(fù)雜度用大寫O表示，所以也稱作大O表示法。算法的時(shí)間復(fù)雜度函數(shù)為：T(n)=O(f(n))沧侥；
T(n)=O(f(n))表示存在一個(gè)常數(shù)C可霎，使得在當(dāng)n趨于正無窮時(shí)總有 T(n) ≤ C * f(n)。簡單來說宴杀，就是T(n)在n趨于正無窮時(shí)最大也就跟f(n)差不多大癣朗。也就是說當(dāng)n趨于正無窮時(shí)T(n)的上界是C * f(n)。其雖然對f(n)沒有規(guī)定旺罢，但是一般都是取盡可能簡單的函數(shù)旷余。
常見的時(shí)間復(fù)雜度有：O(1)常數(shù)型；O(log n)對數(shù)型扁达，O(n)線性型正卧，O(nlog n)線性對數(shù)型，O(n2)平方型`跪解，`O(n3)立方型炉旷，O(nk)k次方型`，`O(2n)指數(shù)型`叉讥。
上圖為不同類型的函數(shù)的增長趨勢圖窘行，隨著問題規(guī)模n的不斷增大，上述時(shí)間復(fù)雜度不斷增大图仓，算法的執(zhí)行效率越低罐盔。
常見的算法時(shí)間復(fù)雜度由小到大依次為：Ο(1)＜Ο(log n)＜Ο(n)＜Ο(nlog n)＜Ο(n^2)＜Ο(n^3)＜…＜Ο(2^n)＜Ο(n!)。
值得留意的是救崔，算法復(fù)雜度只是描述算法的增長趨勢惶看，并不能說一個(gè)算法一定比另外一個(gè)算法高效。這要添加上問題規(guī)模n的范圍帚豪，在一定問題規(guī)范范圍之前某一算法比另外一算法高效碳竟，而過了一個(gè)閾值之后，情況可能就相反了狸臣，通過上圖我們可以明顯看到這一點(diǎn)莹桅。這也就是為什么我們在實(shí)踐的過程中得出的結(jié)論可能上面算法的排序相反的原因。
如何推導(dǎo)時(shí)間復(fù)雜度
上面我們了解了時(shí)間復(fù)雜度的基本概念及表達(dá)式烛亦，那么實(shí)踐中我們怎么樣才能通過代碼獲得對應(yīng)的表達(dá)式呢诈泼？這就涉及到求解算法復(fù)雜度。
求解算法復(fù)雜度一般分以下幾個(gè)步驟：
- 找出算法中的基本語句：算法中執(zhí)行次數(shù)最多的語句就是基本語句煤禽，通常是最內(nèi)層循環(huán)的循環(huán)體铐达。
- 計(jì)算基本語句的執(zhí)行次數(shù)的數(shù)量級：只需計(jì)算基本語句執(zhí)行次數(shù)的數(shù)量級，即只要保證函數(shù)中的最高次冪正確即可檬果，可以忽略所有低次冪和最高次冪的系數(shù)瓮孙。這樣能夠簡化算法分析唐断，使注意力集中在最重要的一點(diǎn)上：增長率。
- 用大Ο表示算法的時(shí)間性能：將基本語句執(zhí)行次數(shù)的數(shù)量級放入大Ο記號中杭抠。
其中用大O表示法通常有三種規(guī)則：
- 用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)脸甘；
- 只保留時(shí)間函數(shù)中的最高階項(xiàng)；
- 如果最高階項(xiàng)存在偏灿，則省去最高階項(xiàng)前面的系數(shù)丹诀；
下面通過具體的實(shí)例來說明以上的推斷步驟和規(guī)則。
時(shí)間復(fù)雜度實(shí)例
常數(shù)階O(1)
無論代碼執(zhí)行了多少行翁垂，只要是沒有循環(huán)等復(fù)雜結(jié)構(gòu)铆遭，那這個(gè)代碼的時(shí)間復(fù)雜度就都是O(1)，如：
int i = 1;
int j = 2;
int k = 1 + 2;
上述代碼執(zhí)行時(shí)沿猜，單個(gè)語句的頻度均為1枚荣，不會(huì)隨著問題規(guī)模n的變化而變化。因此邢疙，算法時(shí)間復(fù)雜度為常數(shù)階棍弄，記作T(n)=O(1)。這里我們需要注意的是疟游，即便上述代碼有成千上萬行，只要執(zhí)行算法的時(shí)間不會(huì)隨著問題規(guī)模n的增長而增長痕支，那么執(zhí)行時(shí)間只不過是一個(gè)比較大的常數(shù)而已颁虐。此類算法的時(shí)間復(fù)雜度均為O(1)。
對數(shù)階O(log n)
先來看對應(yīng)的示例代碼：
int i = 1; // ①
while (i <= n) {
i = i * 2; // ②
}
在上述代碼中卧须，語句①的頻度為1另绩，可以忽略不計(jì)。
語句②我們可以看到它是以2的倍數(shù)來逼近n花嘶，每次都乘以2笋籽。如果用公式表示就是1222…2 <=n，也就是說2的x次方小于等于n時(shí)會(huì)執(zhí)行循環(huán)體椭员，記作2^x <= n车海，于是得出x<=logn。也就是說上述循環(huán)在執(zhí)行l(wèi)ogn次之后隘击，便結(jié)束了侍芝，因此上述代碼的時(shí)間復(fù)雜度為O(log n)。
其實(shí)上面代碼的時(shí)間復(fù)雜度公式如果精確的來講應(yīng)該是：T(n) = 1 + O(log n)埋同，但我們上面已經(jīng)講到對應(yīng)的原則州叠，“只保留時(shí)間函數(shù)中的最高階項(xiàng)”，因此記作O(log n)凶赁。
線性階O(n)
示例代碼：
int j = 0; // ①
for (int i = 0; i < n; i++) { // ②
j = i; // ③
j++; // ④
}
上述代碼中咧栗，語句①的頻度為1逆甜，②的頻度為n，③的頻度為n-1致板，④的頻度為n-1忆绰，因此整個(gè)算法可以用公式T(n)=1+n+(n-1)+(n-1)來表示。進(jìn)而可以推到T(n)=1+n+(n-1)+(n-1)=3n-1可岂，即O(n)=3n-1错敢，去掉低次冪和系數(shù)即O(n)=n，因此T(n)=O(n)缕粹。
在上述代碼中for循環(huán)中的代碼會(huì)執(zhí)行n遍稚茅，因此它消耗的時(shí)間是隨著n的變化而成線性變化的，因此這類算法都可以用O(n)來表示時(shí)間復(fù)雜度平斩。
線性對數(shù)階O(nlogN)
示例代碼：
for (int m = 1; m < n; m++) {
int i = 1; // ①
while (i <= n) {
i = i * 2; // ②
}
}
線性對數(shù)階要對照對數(shù)階 O(log n)來進(jìn)行理解亚享。上述代碼中for循環(huán)內(nèi)部的代碼便是上面講到對數(shù)階，只不過在對數(shù)階的外面套了一個(gè)n次的循環(huán)绘面，當(dāng)然欺税，它的時(shí)間復(fù)雜度就是n*O(log n)了，于是記作O(nlog n)揭璃。
平方階O(n2)
示例代碼：
int k = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
k++;
}
}
平方階可對照線性階來進(jìn)行理解晚凿，我們知道線性階是一層for循環(huán)，記作O(n)瘦馍，此時(shí)等于又嵌套了一層for循環(huán)歼秽，那么便是n * O(n)，也就是O(n * n)情组，即O(n^2)燥筷。
如果將外層循環(huán)中的n改為m，即：
int k = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
k++;
}
}
那么院崇，對應(yīng)的時(shí)間復(fù)雜度便為：O(m * n)肆氓。
同理，立方階O(n3)底瓣、K次方階O(n^k)谢揪，只不過是嵌套了3層循環(huán)、k層循環(huán)而已濒持。
排序算法對比
上面介紹了各種示例算法的時(shí)間復(fù)雜度推理過程键耕，對照上面的時(shí)間復(fù)雜度以及算法效率的大小，來看一下我們常見的針對排序的幾種算法的時(shí)間復(fù)雜度對比柑营。
空間復(fù)雜度
最后屈雄，我們再了解一下空間復(fù)雜度」偬祝空間復(fù)雜度主要指執(zhí)行算法所需內(nèi)存的大小酒奶，用于對程序運(yùn)行過程中所需要的臨時(shí)存儲空間的度量蚁孔，這里的空間復(fù)雜度同樣是預(yù)估的。
程序執(zhí)行除了需要存儲空間惋嚎、指令杠氢、常數(shù)、變量和輸入數(shù)據(jù)外另伍，還包括對數(shù)據(jù)進(jìn)行操作的工作單元和存儲計(jì)算所需信息的輔助空間鼻百。存儲空間通常包括：指令空間（即代碼空間）、數(shù)據(jù)空間（常量摆尝、簡單變量）等所占的固定部分和動(dòng)態(tài)分配温艇、遞歸棧所需的可變空間。其中可變空間與算法有關(guān)堕汞。
一個(gè)算法所需的存儲空間用f(n)表示勺爱。S(n)=O(f(n))其中n為問題的規(guī)模，S(n)表示空間復(fù)雜度讯检。
下面看兩個(gè)常見的空間復(fù)雜度示例：空間復(fù)雜度O(1)和O(n)琐鲁。
空間復(fù)雜度 O(1)
空間復(fù)雜度為O(1)的情況的示例代碼與時(shí)間復(fù)雜度為O(1)的實(shí)例代碼一致：
int i = 1;
int j = 2;
int k = 1 + 2;
上述代碼中臨時(shí)空間并不會(huì)隨著n的變化而變化，因此空間復(fù)雜度為O(1)人灼∥Ф危總結(jié)一下就是：如果算法執(zhí)行所需要的臨時(shí)空間不隨著某個(gè)變量n的大小而變化，此算法空間復(fù)雜度為一個(gè)常量挡毅，可表示為 O(1)蒜撮，即 S(n) = O(1)。
空間復(fù)雜度 O(n)
示例代碼：
int j = 0;
int[] m = new int[n];
for (int i = 1; i <= n; ++i) {
j = i;
j++;
}
上述代碼中跪呈，只有創(chuàng)建int數(shù)組分配空間時(shí)與n的大小有關(guān)，而for循環(huán)內(nèi)沒有再分配新的空間取逾，因此耗绿，對應(yīng)的空間復(fù)雜度為S(n) = O(n)。
總結(jié)一下
本篇文章給大家講了可以通過時(shí)間復(fù)雜度和空間復(fù)雜度來衡量算法的優(yōu)劣砾隅，同時(shí)用具體的實(shí)例來講解如何計(jì)算不同方法的時(shí)間復(fù)雜度和空間復(fù)雜度误阻。當(dāng)我們了解了這些基本的概念、函數(shù)晴埂、計(jì)算方法究反、計(jì)算規(guī)則及算法性能之后，再進(jìn)行算法的學(xué)習(xí)便可以輕松預(yù)估出算法的性能等指標(biāo)儒洛。
參考文獻(xiàn)：
https://blog.csdn.net/zolalad/article/details/11848739 https://zhuanlan.zhihu.com/p/50479555
