演算法時間複雜度(如何快速記住算法複雜度)
演算法時間複雜度(如何快速記住算法複雜度)
資料來源: https://posts.careerengine.us/p/5d6a88dc9ce3d42369a18200
PS 一般標準 n^2
O(1) = 陣列讀取
O(log n) = 二分搜尋
O(nlog n) = 合併排序
O(n) = 簡易搜尋(依序搜尋)
O(n^2) = 選擇排序 (氣泡排序)
O(2^n) = 費波那契數列
O(n^n) = fuck
O(n!) = ORZ
9 thoughts on “演算法時間複雜度(如何快速記住算法複雜度)”
氣泡排序法(Bubble Sort) 時間複雜度 -我的水準(一般)
http://notepad.yehyeh.net/Content/Algorithm/Sort/Bubble/1.php
Best Case：Ο(n)
Worst Case：Ο(n^2)
Average Case：Ο(n^2)
空間複雜度(Space Complexity)：θ(1)
穩定性(Stable/Unstable)：穩定(Stable)
JS code
var swap = function(data, i, j){
var tmp = data[i];
data[i] = data[j];
data[j] = tmp;
};
var bubbleSort = function(data){
var flag = true;
for(var i = 0; i < data.length – 1 && flag; i++){
flag = false;
for(var j = 0; j < data.length – i – 1; j++){
if(data[j+1] < data[j]){
swap(data, j+1, j);
flag = true;
}
}
}
};
簡易搜尋
依序比對搜尋
雙層迴圈搜尋
時間複雜度 O(n) 比 氣排 (氣泡排序) 好
簡易搜尋(依序搜尋) VS 二分搜尋 時間複雜度
資料來源:https://mp.weixin.qq.com/s/rLXlvEAowJCAGu3TMvSvqw
比二分查找更簡單的算法，我能想到的只有遍歷枚舉，說的直白些，就是寫for循環。
我們通常需要在一個數組當中找一個數，這個時候我們可以寫一個for循環去挨個查找，這麼下來，時間複雜度就會是O(n)。
如果我告訴你，這個數組是排序好的，這時我們就可以使用二分查找去找這個數。
O(n) 和O(logn) 可能直接看表達式不夠形象，我舉個例子你就懂了，假設數組長度是4294967296，如果是O(n) 時間的話，最差情況下你需要去找4294967296次，如果是O(logn)，最差情況下你只需要去找32 次。
yeah = YES 比 nice 更好 = 讚
每個程序員都應該收藏的算法複雜度速查表 [所有常用演算法/資料結構的時間複雜度 資料]
https://mp.weixin.qq.com/s?__biz=Mzg2MjEwMjI1Mg==&mid=2247490108&idx=4&sn=850d4f0f3d19e10bd6d2e2545e047a7d&chksm=ce0dadbff97a24a9e9ab5495f37e504f082ed455a3f7568823f20dae0bd48398095911d1d4b5&scene=0&xtrack=1&key=e566f72e668d89c1ed57cede4cf596d06ba286ee3f27bacfc232809617a88de7d538352741a48b21406c6aa85002cd43ff34defc9797716772807622d2668ba09b8436ddf50e81c3aa3777436abba4ab&ascene=1&uin=MjIwODk2NDgxNw%3D%3D&devicetype=Windows+10&version=62070152&lang=zh_TW&pass_ticket=67XGIUragzoDYPlF88OExWG16i%2BWkQZ2APCI%2Bnzev3359leYbAP3QEYuw480dmub
https://www.bigocheatsheet.com/
演算法 等級 分別 區分
程式設計師 等級 靠演算法