分類

展開全部 | 收合全部

分類

展開全部 | 收合全部

【演算法筆記 #2】sorting 時間複雜度(Time and Space Complexity, Big O), Best, Average, Worst Time 整理 #面試準備

前言

sorting 簡單說明 (記憶用)

簡單說明
Selection sort (選擇排序)先完成的排序是「當前index」,從當前往後搜尋全部,找最小
Insertion sort (插入排序)每一層 loop 會完成的是「當前 index」之前的所有排序,也就是說,for-loop 的外層代表處理完成的 index,而內層處理插入當前的哪個位置
Bubble sort (氣泡排序)不斷交換的排序,已交換len=4為例,比較 「(1,2),(2,3,(3,4)) / (1,2),(2,3),(3,4) / (1,2),(2,3),(3,4)」 (共 3組 x 3輪)
Quick sort (快速排序)1.先挑選一個基準 (pivot),經常選最後一個值,後續的數值與基準比大小,建立two pointer,比小往左、比大往右,「停止條件:two pointer 交錯」 / 2.每一輪完成一次「對基準排序」後,將基準擺在中間 / 3. 依據 「divide and conquer (O(logn))」 的概念,完成剩餘的左右兩側(partition)的基準排序 (partition = [0, pivot-1], [pivot], [pivot+1, n-1]) 「停止條件:代表 front,end 的 two pointer 交錯
Merge sort (合併排序)一樣也是「divide and conquer (O(logn))」 的概念,1. 將 array 拆成 n/2,n/2再拆兩個n/4… 2. 拆到剩餘 2 or 1(種子),開始合併,合併時只需要看如何已排序的兩數列如何交錯即可(O(m+n)),使用 two pointer
Heap sort (堆積排序)Complete Binary Tree /Max Heap (root max) / MaxHeapify() = 自上而下調整矩陣 BuildMaxHeap() 1. 最後一個位置換到第一個 / 2.最後一個消失(取得 Max) 3. 自上而下的 MaxHeapify()
Radix sort (基數排序)

sorting 整理

BestWorstAverageSpace Complexity
Selection sortO(n^2)O(n^2)O(n^2)O(1),無新增矩陣等級的空間使用
Insertion sortO(n) 當數列已經是從小到大的O(n^2)O(n^2)|
Bubble sort|
|

特殊情況

  • bubble sort early break: 如果某一回合沒有 swap 發生,直接結束

所以當從小至大排列時,bubble sort 有 best case O(n) -> early break

  • insertion sort : 恰好小至大,免做「插入動作 O(n)

所以當從小至大排列時,insertion sort 有 best case O(n) -> early break

  • quick sort can not divide well: 如果一個矩陣從小到大或從大到小,因為沒辦法好好發揮 divide and conquer 的效果,O(m+n)*O(n) 的 m=0, n=n (類似概念) = O(n^2)

所以當從小至大 or 大至小排列時,quick sort 有 worst case O(n^2)

說明

插入排序法(Insertion Sort) Best case O(n)
直到遇到第一個比正處理的值小的值

快速排序法(Quick Sort) Worst case(On^2)
當資料的順序恰好為由大到小或由小到大時
有分割跟沒分割一樣
(資料太整齊, pivot 產生不了 Divide and conquer的效果)

https://i.imgur.com/1Pe7ksv.png

Reference

Howard Weng
Howard Weng

我是 Howard Weng,很多人叫我嗡嗡。這個網站放了我的各種筆記。希望這些筆記也能順便幫助到有需要的人們!如果文章有幫助到你的話,歡迎幫我點讚哦!
另外,因為定位是「個人的隨手筆記」,有些文章內容「⚠️可能我理解有誤⚠️」或「?只寫到一半?」,如果有發現這樣的情況,歡迎在該文章的最下面留言提醒我!我會儘快修正或補上!感謝大家的建議與幫忙,讓網站能變得更好?

文章: 889

★留個言吧!內容有誤或想要補充也歡迎與我討論!