1.算法概念
計算機科學(xué)中的算法指的就是計算機執(zhí)行的指令。
算法是計算機處理信息的本質(zhì)，因為計算機程序本質(zhì)上是一個算法來告訴計算機確切的步驟來執(zhí)行一個指定的任務(wù)氯析，如計算職工的薪水或打印學(xué)生的成績單登失。
一般地，當(dāng)算法在處理信息時塔逃，會從輸入設(shè)備或數(shù)據(jù)的存儲地址讀取數(shù)據(jù)讯壶，把結(jié)果寫入輸出設(shè)備或某個存儲地址供以后再調(diào)用。
-----------
輸入 --> | 算法 | --> 輸出
-----------
算法的核心是創(chuàng)建問題抽象的模型和明確求解目標(biāo)湾盗，之后可以根據(jù)具體的問題選擇不同的模式和方法完成算法的設(shè)計伏蚊。
2. 時間復(fù)雜度
算法的時間復(fù)雜度是指算法需要消耗的時間資源。
一般來說格粪，計算機算法是問題規(guī)模n 的函數(shù)f(n)躏吊，算法的時間復(fù)雜度也因此記做：
T(n) = O(f(n))
算法執(zhí)行時間的增長率與f(n) 的增長率正相關(guān)，稱作漸近時間復(fù)雜度（Asymptotic Time Complexity）帐萎，簡稱時間復(fù)雜度比伏。
3. 空間復(fù)雜度
算法的空間復(fù)雜度是指算法需要消耗的空間資源。
其計算和表示方法與時間復(fù)雜度類似疆导，一般都用復(fù)雜度的漸近性來表示赁项。
同時間復(fù)雜度相比，空間復(fù)雜度的分析要簡單得多澈段。
4. 大 O 表示法
什么是大 O 表示法悠菜？
我們常常會聽到有人說，“這個算法在最糟情況下的運行時間是 O(n^2) 而且占用了 O(n) 大小的空間”败富，他的意思是這個算法有點慢李剖，不過沒占多大空間。
這里的O(n^2)和O(n)就是我們通常用來描述算法復(fù)雜度的大 O 表示法囤耳。
大 O 表示法能讓你對一個算法的運行時間和占用空間有個大概概念篙顺。大 O 表示法怎么看？怎么用充择？
假設(shè)一個算法的時間復(fù)雜度是 O(n)德玫，n 在這里代表的意思就是數(shù)據(jù)的個數(shù)。舉個例子椎麦，如果你的代碼用一個循環(huán)遍歷 100 個元素宰僧，那么這個算法就是 O(n)，n 為 100观挎，所以這里的算法在執(zhí)行時就要做 100 次工作琴儿。大O符號是關(guān)于一個算法的最壞情況的段化。比如說，你要從一個大小為 100 的數(shù)組（數(shù)組中存的都是數(shù)字）中找出一個數(shù)值等于 10 的元素造成，我們可以從頭到尾掃描一遍显熏，這個復(fù)雜度就是 O(n)，這里 n 等于 100晒屎，實際上呢喘蟆，有可能第 1 次就找到了，也有可能是第 100 次才找到鼓鲁，但是大 O 表示法考慮的是最壞的情況蕴轨，也就是一個算法理論上要執(zhí)行多久才能覆蓋所有的情況。
常見的時間復(fù)雜度有：
常數(shù)階O(1)骇吭，對數(shù)階O(log2n)橙弱，線性階O(n)，線性對數(shù)階O(nlog2n)燥狰，平方階O(n2)棘脐，立方階O(n3)，...碾局， k次方階O(nk)荆残，指數(shù)階O(2n)。隨著問題規(guī)模n的不斷增大净当，上述時間復(fù)雜度不斷增大内斯，算法的執(zhí)行效率越低。-
說明：
- 大部分情況下你用直覺就可以知道一個算法的大 O 表示法
- 大 O 表示法只是一種估算像啼，當(dāng)數(shù)據(jù)量大的時候才有用
- 這種東西僅僅在比較兩種算法哪種更好的時候才有點用俘闯。但歸根結(jié)底，你還是要實際測試之后才能得出結(jié)論忽冻。而且如果數(shù)據(jù)量相對較小真朗，哪怕算法比較慢，在實際使用也不會造成太大的問題僧诚。
要知道一個算法的大 O 表示法通常要通過數(shù)學(xué)分析遮婶。在這里我們不會涉及具體的數(shù)學(xué)，不過知道不同的值意味著什么會很有用湖笨。所以這里有一張方便的表旗扑。n 在這里代表的意思是數(shù)據(jù)的個數(shù)。舉個例子慈省，當(dāng)對一個有 100 個元素的數(shù)組進行排序時臀防，n = 100。
| Big-O | 名字 | 描述 |
|---|---|---|
| O(1) | 常數(shù)級 | 最好的。不論輸入數(shù)據(jù)量有多大袱衷，這個算法的運行時間總是一樣的捎废。例子: 基于索引取出數(shù)組中對應(yīng)的元素。 |
| O(log n) | 對數(shù)級 | 相當(dāng)好致燥。這種算法每次循環(huán)時會把需要處理的數(shù)據(jù)量減半登疗。如果你有 100 個元素，則只需要七步就可以找到答案篡悟。1000 個元素只要十步谜叹。100,0000 元素只要二十步匾寝。即便數(shù)據(jù)量很大這種算法也非嘲嵩幔快。例子：二分查找艳悔。 |
| O(n) | 線性級 | 還不錯急凰。如果你有 100 個元素，這種算法就要做 100 次工作猜年。數(shù)據(jù)量翻倍那么運行時間也翻倍抡锈。例子：線性查找。 |
| O(n log n) | 線性對數(shù)級 | 還可以乔外。比線性級差了一些床三，不過也沒那么差勁。例子：最快的通用排序算法杨幼。 |
| O(n^2) | 二次方級 | 有點慢撇簿。如果你有 100 個元素，這種算法需要做 100^2 = 10000 次工作差购。數(shù)據(jù)量 x 2 會導(dǎo)致運行時間 x 4 (因為 2 的 2 次方等于 4)四瘫。例子：循環(huán)套循環(huán)的算法，比如插入排序欲逃。 |
| O(n^3) | 三次方級 | 特別慢找蜜。如果你有 100 個元素，那么這種算法就要做 100^3 = 100,0000 次工作稳析。數(shù)據(jù)量 x 2 會導(dǎo)致運行時間 x 8洗做。例子：矩陣乘法。 |
| O(2^n) | 指數(shù)級 | 超級慢彰居。這種算法你要想方設(shè)法避免诚纸，但有時候你就是沒得選。加一點點數(shù)據(jù)就會把運行時間成倍的加長裕菠。例子：旅行商問題咬清。 |
| O(n!) | 階乘級 | 比蝸牛還慢！不管干什么都要跑個 N 年才能得到結(jié)果。 |
大部分情況下你用直覺就可以知道一個算法的大 O 表示法旧烧。比如說影钉，如果你的代碼用一個循環(huán)遍歷你輸入的每個元素，那么這個算法就是 O(n)掘剪。如果是循環(huán)套循環(huán)平委，那就是 O(n^2)。如果 3 個循環(huán)套在一起就是 O(n^3)夺谁，以此類推廉赔。
注意，大 O 表示法只是一種估算匾鸥，當(dāng)數(shù)據(jù)量大的時候才有用蜡塌。舉個例子，[插入排序](Insertion Sort/)的最糟情況運行時間是 O(n^2)勿负。 理論上來說它的運行時間比[歸并排序](Merge Sort/)要慢一些馏艾。歸并排序是 O(n log n)。但對于小數(shù)據(jù)量奴愉，插入排序?qū)嶋H上更快一些琅摩，特別是那些已經(jīng)有一部分?jǐn)?shù)據(jù)是排序好的數(shù)組。
