效率的重要性
在介紹大 O 表示法前，先看個簡單的例子。假設(shè)你的郵箱中有 10 封郵件左痢，其中一封郵件有你需要的電話號碼，在不使用搜索功能的前提下系洛，如何找到這封郵件呢俊性？
由于只有 10 封郵件，你可以逐一打開郵件瀏覽描扯，直到找到所需電話號碼的那封定页，總得來說問題不大，最多花個一兩分鐘绽诚。那如果郵箱里有 18 億封郵件呢典徊？面對這么龐大的規(guī)模，你絕對不會像剛才那樣挨個打開查找恩够，因為就算檢查每封郵件只需 1 秒卒落，你也需要不眠不休得花上 57 年才能找到需要的那封。
這個例子告訴我們玫鸟，在小規(guī)模范圍內(nèi)運(yùn)作良好的方法导绷，一旦規(guī)模擴(kuò)大就會變得不再適用。如果真的有那么多郵件屎飘，我們最先想到的就是通過全局搜索匹配來節(jié)約時間妥曲。
復(fù)雜度是什么
衡量算法的高效與否的標(biāo)準(zhǔn)有兩個：
- 花更少的時間
- 花更少的空間
這兩點(diǎn)分別對應(yīng)時間復(fù)雜度和空間復(fù)雜度。舉個例子：商場購物
開車購物法 — 開一輛大車去商場钦购，一趟買完所有的東西回家檐盟。
步行購物法 — 拎個口袋步行去商場，分幾趟買完所有的東西押桃。
開車購物法可以節(jié)省時間葵萎，但是要求你有一輛大車，該方法時間復(fù)雜度低，空間復(fù)雜度高羡忘；步行購物法可以省空間谎痢，但是要求你往返好幾趟，該方法時間復(fù)雜度高卷雕，空間復(fù)雜度低节猿。因此，現(xiàn)實(shí)生活中遇到類似的問題我們需要權(quán)衡漫雕。
大 O 表示法是什么
大 O 符號是用來描述算法復(fù)雜度的語言滨嘱，用它來反應(yīng)不同算法處理問題的效率。算法的效率體現(xiàn)在：當(dāng)輸入的任意增長時浸间，算法相對輸入的運(yùn)行時增長速度太雨。
簡單分析
- 輸入任意增長 — 大 O 表示法關(guān)心的是，隨著輸入 n 增長而增長最快速的部分魁蒜，因為當(dāng) n 變得非常大時囊扳，其余的影響顯得微不足道。
- 運(yùn)行時增長速度 — 算法的運(yùn)行時間取決于處理器的性能梅惯，因此很難確定其準(zhǔn)確的運(yùn)行時間宪拥。所以大 O 表示法討論的是運(yùn)行時的增長速度 。
- 相對輸入 — 大 O 表示法可以衡量運(yùn)行時的增長速度铣减，如 “算法效率和輸入成線性關(guān)系”（O(N)）
O(1) — 常數(shù)時間
這表示該算法的運(yùn)行時是固定的她君，即無論輸入多少數(shù)據(jù)，算法都將花費(fèi)相同的時間葫哗。舉個例子缔刹，下面的方法接收一個數(shù)組，不管傳遞的數(shù)組中的元素數(shù)量是 1 還是 1000劣针，所花的時間是一致的校镐，因為該方法只是簡單得返回數(shù)組中的第一個元素。
function(array) {
return array[0];
}
趨勢圖如下：
O(1)
O(n) — 線性時間
對于上面郵件的例子捺典，這相當(dāng)于手動查看所有的郵件鸟廓。隨著數(shù)組中元素數(shù)量增加，處理所需的時間也以相同的速率增加襟己。舉個例子引谜，下面的方法將傳入的數(shù)組的元素打印出來，console.log() 方法執(zhí)行的次數(shù)取決于數(shù)組的長度擎浴。
function logArray(array) {
for (let i = 0; i < array.length; i++) {
console.log(array[i]);
}
}
趨勢圖如下
O(n)
O(N2), O(N3), O(N?)??— 平方時間, 立方時間, 四次方時間
算法復(fù)雜度為 O(N2) 的典型標(biāo)志是代碼中出現(xiàn)循環(huán)嵌套：
function(array){
for (let i = 0; i < array.length; i++){
for (let j = 0; j < array.length; j++){
console.log(array[j]);
}
}
}
下圖給出 O(N) 和 O(N2) 的增長趨勢對比：
藍(lán)色: O(N) · 紅色: O(N2)
同理员咽，還有 O(N3)、 O(N?) 只要多嵌套幾層循環(huán)贮预，運(yùn)行時也會隨之急速增長贝室。
藍(lán)色: O(N) · 紅色: O(N2) · 綠色: O(N3) · 橘黃色: O(N?)
O(logN) — 對數(shù)時間
算法時間復(fù)雜度為 O(logN) 的例子是二分查找契讲，二分查找的思路是：將要查找的數(shù)與當(dāng)前數(shù)組中心值進(jìn)行比較，每次比較過濾掉當(dāng)前數(shù)組的一半滑频，因此非常高效捡偏。如下圖
</center>
O(logN) 的增長趨勢圖：
紫色: O(logN)
忽略常量
下面的方法對傳入的數(shù)組執(zhí)行兩次相同的操作：
function countUpThenDown(array) {
for (let i = 0; i < array.length; i++) {
console.log(i);
};
for (let i = array.length; i > 0; i--) {
console.log(i);
};
}
很容易想到該方法的算法效率為 O(2N)。如果在方法中再加一個非嵌套的循環(huán)峡迷，將執(zhí)行 3 次相同的操作霹琼，算法效率為 O(3N)。在數(shù)據(jù)規(guī)模很小的情況下凉当，這點(diǎn)差異是很重要的。但是大 O 表示法更加關(guān)注的是大規(guī)模數(shù)據(jù)下的性能表現(xiàn)售葡，因此通常忽略常量倍數(shù)看杭，從下面的圖表就可以看到。
藍(lán)色: O(N) · 紅色: O(2N) · 綠色: O(3N).
</center>
藍(lán)色: O(N) · 紅色: O(2N) · 綠色: O(3N).
圖一顯示了 O(N) 挟伙、 O(2N)楼雹、O(3N) 在小規(guī)模下的差異，圖二顯示這種差異在大規(guī)模的情況下微不足道尖阔。
只關(guān)心最高次冪
很少會看到函數(shù)的時間復(fù)雜度被表示成 O(N2 + N) 贮缅。實(shí)際上 O(N2 + N) 和 O(N2) 的差異只是隨著 N 的增加 Y 軸上移 N 個單位，如下圖
藍(lán)色: (N2 + N) · 紅色: O(N2).
可以看到?jīng)Q定真正走勢的是 N2介却，因此在許多情況下谴供，將表達(dá)式縮減到對算法影響最大的元素就夠了。有了這套規(guī)則齿坷，通常將算法時間復(fù)雜度為 O(2N3 + 5N2 + 4N + 7) 縮寫成 O(N3)桂肌。
考慮的是最差情況
function findTheMeaningOfLife(array){
for (let i = 0; i < array.length; i++) {
if (array[i] === 42) {
return i;
}
}
}
例如上面的方法很有可能會提前結(jié)束，但是大 O 表示法考慮的是最差的情況永淌，因此該方法的時間復(fù)雜度還是 O(N)崎场。
空間復(fù)雜度
大 O 也可以用來表示空間復(fù)雜度 。當(dāng)討論空間復(fù)雜度時遂蛀，我們關(guān)注的是算法在運(yùn)行時額外分配的內(nèi)存空間谭跨。
function sayHiNTimes(n) {
for (let i = 0; i < n; i++) {
console.log('hi');
}
}
上面的方法空間復(fù)雜度是 O(1) ，因為整個過程只用到一個固定的變量李滴。
function arrayOfHiNTimes(n) {
const hiArray = [];
for (let i = 0; i < n; i++) {
hiArray[i] = 'hi';
}
return hiArray;
}
上面的方法空間復(fù)雜度是 O(N) 螃宙，因為 hiArray 的長度隨著 n 的增大而增大。
COVER FROM：http://rkhcy.github.io/2019/03/06/bigO/
