中位數和順序統計學

最大值和最小值

應該很簡單是 $\Theta(n)$ 的複雜度。

1. 最大或最小 直接遍歷就可以了。

2. 最大和最小 普遍的方法是執行 2 遍上一過程。對規模為 n 的輸入來說，至多比較 $2n -2$ 次。

   但實際上也有更好的辦法，比較 $3\lfloor n / 2 \rfloor$ 次。 成對處理資料，先將一對資料進行比較，將大的和現在的最大值進行比較，小的和現在的最小值進行比較。 這樣，每對資料需比較 3 次。

選擇問題

1. 期望為 $\Theta(n)$ 的隨機選擇 感覺確實之前想不到這樣的辦法。=_= 本質也是劃分大問題為小問題。用隨機的主元元素將陣列劃分，計算比主元大的數目，如果比 i 大的話就在劃分高區再找，比 i 小的話則在另一個裡面。

2. 最壞為 $\Theta(n)$ 選擇演算法

   1. 將輸入陣列的 n 個元素劃分為 $\lceil n / 5 \rceil$ ，僅有一組可能不是 5 個元素。
   2. 尋找每一組的中位數，排序後選擇即可。
   3. 遞迴呼叫自己，找到所有中位數的下中位數 $x$。
   4. 將下中位數作為主元進行劃分。
   5. 判斷並分割槽遞迴尋找。

   這個被證明是最壞 $\Theta(n)$ ，直覺上有點不能理解為什麼是 5 不是其他數字。如果是 3 或者 7 呢？

資料結構

很多以前學過的就不寫了。

散列表(Hash Table)

• 散列表 儘可能達到 $O(1)$ 的時間複雜度。

• 雜湊函式

  1. 乘法雜湊 $$ h(k) = \lfloor m(k A \mod 1) \rfloor $$
  2. 全域雜湊 設 $ H $ 為有限的一組雜湊函式，它將給定的關鍵字域 $U$ 對映到 $ { 0, 1, ···, m-1 } $ 中。 這樣的函式族稱為是全域的，如果對每一對不同的關鍵字 $k,l \in U$ ，滿足 $h(k) = h(l)$ 的雜湊函式 $ h \in H $ 的個數至多為 $|H| / m$ 。

• 開放定址法

  • 特性

    不使用連結串列形式儲存，所有的值(或者值的指標)都在同一散列表裡。查詢的時候必須按照當時插入的時候的演算法進行逐個檢視，直到值為空時再判斷是否沒有。 但是在執行刪除操作時，不能僅將當時的位置的值設為 NUL，否則會出現之後的值都無法被檢索的錯誤。 解決方法是在這個地方插入一個特殊的 DELETED 的值。同時，查詢時間就不再依賴於裝載因子 $alpha$ 了。 因此在必須存在刪除操作的散列表中，一般使用連結法來解決碰撞。

  • 計算探查序列

    1. 線性探查 依次線性查詢。 可能會出現一次群集的現象。導致連續佔用的槽不斷增加。

    2. 二次探查 偏移量為二次函式。

    3. 雙重雜湊 偏移量由另一個雜湊函式決定。

• 完全雜湊

  • 性質 當關鍵詞集合是靜態的時候，可以達到相當好的最壞情況效能($O(1)$)。

  • 基本想法 利用一種兩級的雜湊方案，每一級都使用全域雜湊。確保二次散列表中不出現碰撞，且總儲存空間為 $O(n)$。