演算法時間複雜度(如何快速記住算法複雜度)
演算法時間複雜度(如何快速記住算法複雜度)
資料來源: 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
11 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/
演算法 等級 分別 區分
程式設計師 等級 靠演算法
實力不夠 設備來湊(自己寫演算法時間複雜度太高 ，那就把SQL 包裝成函數一部分 替代高複雜度部分) ~5W2H1R
EX:[檢核購物車商品的配料選擇未符合的清單]
//增加 AND (a.item_type='P' OR a.item_type='TP') AND a.del_flag='N'
//刪除 AND a.parent_item_no=0//
//增加 IFNULL(f.item_name,'') AS parent_name
//增加 LEFT JOIN order_content_data f
//--------------------------------------------//
SELECT x.*
FROM (
SELECT a.order_no,IFNULL(f.item_name,'') AS parent_name,a.parent_item_no,a.item_no,a.item_sid AS product_sid,
a.item_name AS product_name,
d.SID AS condiment_group_sid,
d.group_name,d.required_flag,d.max_count,d.min_count,
IFNULL(SUM(e.item_count),0) AS select_count
FROM order_content_data a
JOIN product_condiment_relation b
ON b.product_sid=a.item_sid
JOIN condiment_data c
ON c.SID=b.condiment_sid
AND c.del_flag='N'
JOIN condiment_group d
ON d.SID=c.group_sid
AND d.del_flag='N' AND d.required_flag='Y'
LEFT JOIN order_content_data e
ON e.order_no=a.order_no
AND e.parent_item_no=a.item_no
AND e.item_type='C'
AND e.del_flag='N'
AND e.item_sid=c.SID
LEFT JOIN order_content_data f
On f.order_no=a.order_no
AND f.item_no=a.parent_item_no
WHERE a.order_no='20251013-0001'
AND (a.item_type='P' OR a.item_type='TP') AND a.del_flag='N'
Group by a.order_no,a.item_no,d.SID
) x
WHERE (x.select_count=0)
OR (x.select_count > 0
AND (
(x.select_count < x.min_count) OR (x.select_count > x.max_count)
)
) ORDER BY item_no,condiment_group_sid DESC
C# 實際函數
public bool CondimentCheckMin_Count(ref string strShowMsg,string strOrderNo="",string strItemNo="")//配料最少量檢查
{
//檢核購物車商品的配料選擇未符合的清單
strShowMsg = "";
bool blnResult = false;
string OrderNo = (strOrderNo.Length > 0) ? strOrderNo : m_StrPosOrderNumber;
string strSQLConditional = $"a.order_no='{OrderNo}' " + ((strItemNo.Length > 0) ?$"AND a.item_no='{strItemNo}'" :"");
string SQL = @"SELECT x.*
FROM (
SELECT a.order_no,IFNULL(f.item_name,'') AS parent_name,a.parent_item_no,a.item_no,a.item_sid AS product_sid,
a.item_name AS product_name,
d.SID AS condiment_group_sid,
d.group_name,d.required_flag,d.max_count,d.min_count,
IFNULL(SUM(e.item_count),0) AS select_count
FROM order_content_data a
JOIN product_condiment_relation b
ON b.product_sid=a.item_sid
JOIN condiment_data c
ON c.SID=b.condiment_sid
AND c.del_flag='N'
JOIN condiment_group d
ON d.SID=c.group_sid
AND d.del_flag='N' AND d.required_flag='Y'
LEFT JOIN order_content_data e
ON e.order_no=a.order_no
AND e.parent_item_no=a.item_no
AND e.item_type='C'
AND e.del_flag='N'
AND e.item_sid=c.SID
LEFT JOIN order_content_data f
On f.order_no=a.order_no
AND f.item_no=a.parent_item_no
WHERE " + strSQLConditional +
@" AND (a.item_type='P' OR a.item_type='TP') AND a.del_flag='N'
Group by a.order_no,a.item_no,d.SID
) x
WHERE (x.select_count=0)
OR (x.select_count > 0
AND (
(x.select_count x.max_count)
)
) ORDER BY item_no,condiment_group_sid DESC";
DataTable DTBuf= SQLDataTableModel.GetDataTable(SQL);
if(DTBuf!=null && DTBuf.Rows.Count > 0 )
{
blnResult = true;
strShowMsg = "";
for (int i = 0; i 0)?$"套餐「{strParentName}」下":"";
strContent+= DTBuf.Rows[i]["product_name"].ToString();
if ((count < min) && (count max)
{
strContent += $"的「{DTBuf.Rows[i]["group_name"].ToString()}」超過選取範圍: {min} ~ {max} 設定";
}
else
{
strContent = "";
}
if(strContent.Length>0)
{
if (strShowMsg.Length == 0)
{
strShowMsg = strContent;
}
else
{
strShowMsg += "\n" + strContent;
}
}
}
}
if (strShowMsg.Length == 0)
{
blnResult = false;
}
else
{
strShowMsg += "\n您還要繼續執行結帳嗎?";
}
return blnResult;
}