演算法十八般武藝
簡介:給定一數 n 作為版本,該數內存在一值為壞掉的版本,而該值後的數字皆為壞掉的版本,求該值。
嘗試一:線性搜尋 (Linear Search)
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
簡介
- 實作難易度:簡單
- 最佳時間複雜度:
- 最壞時間複雜度:
- 平均時間複雜度:
概念
根據題目,我們可以用單純從到逐一判斷是否是壞掉的版本,而第一個遇到的壞掉的版本即是答案:
執行結果
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
TLE原因
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
根據該演算法推算,若給定一邊緣測資:
則該測資的時間複雜度為,每次迭代若花費ms,則需花費小時執行。
不論是由頭或是尾端開始線性搜尋,若測資過於極端,將會導致TLE。
嘗試二:指數搜尋 (Exponential search) / 深度優先搜尋(Depth-First-Search, a.k.a DFS)
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
簡介
- 實作難易度:簡單
- 最佳時間複雜度:
- 最壞時間複雜度:
- 平均時間複雜度:
以指數搜尋為例
概念
指數搜尋利用指數的成長性來逐步擴大搜尋範圍,並直到指數超過/到達所搜尋的值,後利用其他搜尋演算法於該值域進行二次搜尋。
執行結果
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
TLE原因
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
由於DFS用在數列上的效果和指數搜尋是相同的,所以我們放在一起討論。
根據指數底數的不同,對於增長的速度也會有所不同,若根據題目的邊緣測資:
當我們使用作為底數,要迭代次才能得到範圍進行下一步的搜尋;
當我們使用作為底數,只要迭代次就能得到範圍進行下一步的搜尋,但對於後續的搜尋因為範圍過大,反而會導致搜尋效率低落。
嘗試三:二分搜尋法 (Binary Search)
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
簡介
- 實作難易度:中等
- 最佳時間複雜度:
- 最壞時間複雜度:
- 平均時間複雜度:
概念
根據題目,我們可以藉由判斷是否是壞掉的版本來縮小搜尋範圍,若是壞掉的版本,則第一個壞掉的版本不是這個壞掉的版本就是在這個之前。
執行結果
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
嘗試四:插值搜尋 (Interpolation Search)

簡介
- 實作難易度:中等
- 最佳時間複雜度:
- 最壞時間複雜度:
- 平均時間複雜度:
概念
同二分搜尋,差異在於使用插值公式來計算猜測搜尋鍵值的位置。
實作
基於其公式的要求,該公式要求給定要搜尋的值 key ,故本題不適用。
嘗試一:猴子排序(Bogo Sort)

簡介
- 實作難易度:簡單
- 最佳時間複雜度:
- 最壞時間複雜度:
- 平均時間複雜度:
概念
猴子排序的概念同 無限猴子定律,即每次檢查若未整齊排序,則全部打散再重複執行,直到整齊排序。
猴子排序在極小的陣列中效果和一般的排序是幾乎沒有差異的,但隨著陣列越大,其不可靠性也就越大。
執行結果

TLE原因
由於其極高的不穩定性,導致每次迭代對於次迭代是無影響的,也就是說,每次的時間花費對於整齊排序這個目標是沒有實質幫助的。
嘗試二:臭皮匠排序 (Stooge Sort)

簡介
- 實作難易度:簡單
- 最佳時間複雜度:
- 最壞時間複雜度:
- 平均時間複雜度:
概念
根據Wikipedia的實現:
- 如果最後一個值小於第一個值,則交換這兩個數
- 如果當前集合元素數量大於等於:
-
- 使用臭皮匠排序法排序前的元素
-
- 使用臭皮匠排序法排序後的元素
-
- 再次使用臭皮匠排序法排序前的元素
執行結果

TLE原因

根據演算法的最壞時間複雜度,代入該題的最大上限值,可以發現最大的迭代次數約為次,不考慮比較數字所花費的時間,顯然使用該演算法仍不符合效益。
嘗試三:慢速排序 (Slow Sort)

簡介
- 實作難易度:中等
- 最佳時間複雜度:
- 最壞時間複雜度:
- 平均時間複雜度: or for any
概念
根據Wikipedia,慢速排序基於合併排序的分而治之及遞迴的思想,並故意設計使排序過程非常緩慢。
執行結果

TLE原因
根據演算法的最壞時間複雜度,代入該題的最大上限值 ,可以發現最大的迭代次數約為1.2031481e+22次,不考慮比較數字所花費的時間,顯然使用該演算法仍不符合效益。
嘗試四:泡沫排序 (Bubble Sort)

簡介
- 實作難易度:中等
- 最佳時間複雜度:
- 最壞時間複雜度:
- 平均時間複雜度:
概念
藉由重複走訪過要排序的數列,一次比較兩個元素並交換,直到整齊排序。該演算法得名於其操作過程中元素逐漸浮 到數列的頂端。
執行結果

TLE原因
根據演算法的最壞時間複雜度,代入該題的最大上限值,可以發現最大的迭代次數約為次,不考慮比較數字所花費的時間,顯然使用該演算法仍不符合效益。
嘗試五:快速排序 (Quick Sort)

簡介
- 實作難易度:中等 至 困難
- 最佳時間複雜度:
- 最壞時間複雜度:
- 平均時間複雜度:
概念
根據Wikipedia,快速排序使用分治法(Divide and conquer)策略來把一個序列(list)分為較小和較大的個子序列,然後遞迴地排序兩個子序列。
上面的程式碼採用原地 (in-place) 分割
執行結果

RE原因
根據上面的程式碼,我們會發現該程式碼的空間複雜度會根據數列大小而增加,因此我們觀察得該題的空間複雜度可能有限制。
註:Wikipedia指出快速排序會因不同的實作而空間複雜度有所不同
嘗試六:選擇排序 (Selection Sort)

簡介
- 實作難易度:中等
- 最佳時間複雜度:
- 最壞時間複雜度:
- 平均時間複雜度:
概念
選擇排序會依序將數列內未排序的最小(大)數值排入已排序的數列內,根據大小來決定排序方向性。
執行結果

TLE原因
根據演算法的最壞時間複雜度,代入該題的最大上限值,可以發現最大的迭代次數約為次,不考慮比較數字所花費的時間,顯然使用該演算法仍不符合效益。
嘗試七:合併排序 (Merge Sort)

簡介
- 實作難易度:困難
- 最佳時間複雜度:
- 最壞時間複雜度:
- 平均時間複雜度:
概念
根據Wikipedia,合併排序採用分治法:
- 分割:遞迴地把當前序列平均分割成兩半。
- 整合:在保持元素順序的同時將上一步得到的子序列整合到一起(合併)。
執行結果

備註
由於本題有空間複雜度的限制,所以上面的程式碼採用迭代版本,而非遞迴版本。
嘗試八:堆積排序 (Heap Sort)

簡介
- 實作難易度:中等
- 最佳時間複雜度:
- 最壞時間複雜度:
- 平均時間複雜度:
概念
根據Wikipedia,堆積排序是指利用堆積這種資料結構所設計的一種排序演算法。
執行結果

嘗試九:計數排序 (Counting Sort)

簡介
- 實作難易度:簡單
- 最佳時間複雜度:
- 最壞時間複雜度:
- 平均時間複雜度:
概念
根據Wikipedia,計數排序使用一個額外的陣列,其中第個元素是待排序陣列中值等於的元素的個數。然後根據陣列來將中的元素排到正確的位置。
執行結果

嘗試十:鴿巢排序 (Pigeonhole Sort)

簡介
- 實作難易度:簡單
- 最佳時間複雜度:
- 最壞時間複雜度:
- 平均時間複雜度:
概念
根據Wikipedia,計數排序是一種時間複雜度為且在不可避免遍歷每一個元素並且排序的情況下效率最好的一種排序演算法。
執行結果

嘗試十一:閃電排序 (Flash Sort)

簡介
- 實作難易度:中等至困難
- 最佳時間複雜度:
- 最壞時間複雜度:
- 平均時間複雜度:
概念
閃電排序是桶排序(Bucket Sort)的優化版,主要的優化有:
- 減少多餘的bucket創建,從而減少記憶體使用
- bucket數量由待排序數列的長度決定
元素會藉由下式決定期望放入的bucket:
需要注意的是分母 有可能為0(若max和min的初始化皆為0),而此式的成立會取決於編譯器對於IEEE 754的實作而有所不同。
上面的程式碼的最終排序使用鴿巢排序。
執行結果

嘗試十二:基數排序 (Radix Sort)

簡介
- 實作難易度:中等至困難
- 最佳時間複雜度:
- 最壞時間複雜度:
- 平均時間複雜度:
概念
基數排序將數列中每個數字按位元數切割成不同的數字,然後按每個位數分別比較,藉此達成排序的目的。基數排序的實作方式可分為LSD(Least significant digital)及MSD(Most significant digital),其差異在於排序的開始端。
執行結果
