26 docs tagged with "algorithms"

Big O Notation 是一種表示演算法複雜度的方式。同樣解決一個演算法問題，若該算法執行的時間越少，使用的記憶體愈少，就是越好的解法。可以用來評斷該演算法的好壞。

這篇介紹陣列本身操作的時間複雜度

這篇介紹物件本身操作的時間複雜度

Binary Search 是一種更快的搜尋方式，比起 Liner Search 每次查找時只會排除一個元素，Binary Search 每次查找比對後可以排除掉當前資料量的一半元素。但 Binary Search 只能用在排序過的資料。

一種排序資料的方式，實務上不太常使用，除了某些特定情境。相對於其他排序方式，Bubble Sort 效能較差。

Bucket Sort 和之前的 Radix Sort 有點類似，建立幾個桶子並將資料丟進去排序。而 Bucket Sort 是取區間，例如 1 號桶子裝 0 ~ 9 的數值， 2 號桶子裝 1 ~ 19 的數值，以此類推。

Counting Sort 是以數字為基礎的排序演算法，其需要定義最大範圍值，作為排序用，整體算法較簡單且速度較快，缺點就是排序元素需要確定在最大範圍值內且需要額外空間儲存做運算。

此演算法是由一位叫 Edsger Dijkstra 的荷蘭工程師所發明，他在電腦科學領域貢獻了許多奠定目前網際網路、電腦科學與數位服務等等的基礎。

將一組資料切分成兩組或多組資料，再用切分後的資料進行處理。此技巧能有效減少時間複雜度。

解決一個問題時，若此問題可以分解成多個重複性的子問題，且這些子問題的解答可以構成最終該問題的解答，則我們可以用 Dynamic Programming 的技巧，透過紀錄這些重複多次的子問題的解答，可以有效減少許多執行重複計算同樣問題。

Floyd 判圈算法 (Floyd Cycle Detection Algorithm)，又稱龜兔賽跑算法 (Tortoise and Hare Algorithm)。

Frequency Counter 是一種解題技巧，它使用物件的屬性來記錄陣列或字串裡面特定值的出現次數。它可以避免使用遞迴的方式來計算，可以有效減少時間複雜度。

Heap Sort 使用 Binary Heap 處理資料排序，也可視為 Selection Sort 的改良版。

從第二個元素開始，往前比對，如果比前一個元素小，則交換位置，以此類推。

Linear Search 非常常見，甚至在學迴圈時就已經學過了。以下直接給範例練習！

Merge Sort 是一種透過切分資料再一一合併的排序演算法。

Multiple Pointers 技巧是透過建立 pointer 變數代表目前指到哪個位置 (index)。使用兩個 pointer 代表目前查找的位置與範圍，不用再額外宣告物件或陣列來儲存或遞迴查找。此技巧能有效減少時間與空間複雜度。

Quick Sort 使用基準值 (pivot) 比對排序，並透過 Recursion 的技巧，不斷將每個元素放到正確的位置上。

在這篇之前的排序法都可以用在任何可以比較的資料上，例如一個含有帳戶資料的陣列，按照每個帳戶的 ID 、更新時間、名字、帳戶餘額等等來排序。

Recursion 的定義是一個會呼叫自己的函式。

Selection Sort 實作上是遍歷一次陣列，找出最小值，並將最小值與陣列的第一個值交換，以此類推，再遍歷一次陣列 (先前排序好的位置可以略過) 找出最小值，並將最小值與陣列的第二個值交換。

Shell Sort 是 Insertion Sort 的改良版，加入了間距 (Gap) 的概念將資料分成小區塊，將整組資料分組，每區塊用 Insertion Sort 比對排列，下輪間距變小再進行一次分組與比對，直到間距為 1 時比對完成即結束。

Sliding Window 跟上篇 Multiple Pointers 類似，定義兩個指標，一個是 start，一個是 end。

在上篇我們講到的複雜度表示都是指時間複雜度，在輸入的參數越多越大的情況下，所要執行的步驟(執行所需花費的時間)的增長趨勢。

Timsort 是由 Tim Peter 結合 Merge Sort 與 Insertion Sort 改良所設計出來的。

Tree Sort 簡而言之就是使用 Tree 結構來排序資料，建議先看資料結構篇章中的 Binary Search Tree 和 Tree Traversal ，再回來看這篇會很好理解。