算法圖解第一章筆記與習題（算法簡介）

文章目錄

• 算法圖解第一章筆記與習題（算法簡介）
• • 1.2 二分查找
  • 1.3大$O$表示法
  • 1.4 小結
  • 練習
  • • • 習題1.1
      • 習題1.2
    • 使用大$O$表示法給出下述各種情形的運作時間。（電話簿以姓氏排序）
    • • 習題1.3
      • 習題1.4
      • 習題1.5
      • 習題1.6

1.2 二分查找

def binary_search(list, item):
    # low 和 high 用于跟蹤要在其中查找的部分
    low = 0
    high = len(list) - 1
 
    # 隻要範圍沒有縮小到隻有一個元素，就繼續循環
    while low <= high:
        # 檢查中間的元素
        mid = (low + high) // 2  # 這裡注意下，必須是 // 而不是 /，否則不會自動取整，在list中取非整數則會報錯。
        guess = list[mid]
        # 如果猜的數是對了，傳回結果
        if guess == item:
            return mid
            # 如果猜的數大了，上限減1
        if guess > item:
            high = mid - 1
            # 如果猜的數小了，下限加1
        else:
            low = mid + 1
 
    # 如果沒有這個元素，傳回None
    return None
 
my_list = [1, 3, 5, 7, 9] ##測試資料
           

1.3大 O O O表示法

大 O O O表示法指出的是最糟情況下的運作時間

下面按從快到慢的順序列出經常遇到的5種大O運作時間：

• O ( log ⁡ n ) O(\log n) O(logn)：對數時間，這樣的算法包括二分查找。
• O ( n ) O(n) O(n)：線性時間，這樣的算法包括簡單查找。
• O ( n ∗ log ⁡ n ) O(n * \log n) O(n∗logn)：這樣的算法包括快速排序。
• O ( n 2 ) O(n^2) O(n2)：這樣的算法包括選擇排序。
• O ( n ! ) O(n!) O(n!)：這樣的算法包括旅行商問題的解決方案。

算法的速度指的并非時間，而是操作數的增速！

1.4 小結

• 二分查找的速度比簡單查找要快許多，資料越大，差距就越明顯。
• O ( log ⁡ n ) O(\log n) O(logn)比 O ( n ) O(n) O(n)快。需要搜尋的元素越多，前者比後者就快得越多。
• 算法運作時間并不以秒為機關。
• 算法運作時間是從其增速的角度來度量的。
• 算法運作時間用大 O O O表示法表示。

練習

習題1.1

• 假設有一個包含128個名字的有序清單，你要使用二分查找在其中查找一個名字，請問最多需要幾步才能找到？

log ⁡ 2 128 = 7 步 \log_2128=7步 log2​128=7步

習題1.2

• 上面清單的長度翻倍後，最多需要幾步？

log ⁡ 2 256 = 8 步 \log_2256=8步 log2​256=8步

• 使用大 O O O表示法給出下述各種情形的運作時間。（電話簿以姓氏排序）

習題1.3

• 在電話簿中根據名字查找電話号碼。

二分查找，為 O ( log ⁡ 2 n ) O(\log_2 n) O(log2​n)。

習題1.4

• 在電話簿中根據電話号碼查找人。（提示：你必須查找整個電話簿。）

簡單查找，為 O ( n ) O(n) O(n)。

習題1.5

• 閱讀電話簿中每個人的電話号碼。

簡單查找，為 O ( n ) O(n) O(n)。

習題1.6

• 閱讀電話簿中姓名以A打頭的人的電話号碼。這個問題比較棘手，它涉及到第4章的概念。答案可能讓你感到驚訝！

簡單查找，同時，因為大 O O O表示法沒有常數部分，是以 O ( n 26 ) O(\frac n{26}) O(26n​)直接被看作為 O ( n ) O(n) O(n)。