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

文章目錄

• 算法圖解第一章筆記與習題（算法簡介）
• • 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 = 0high = len(list) - 1# 只要范圍沒有縮小到只有一個元素，就繼續循環while low <= high:# 檢查中間的元素mid = (low + high) // 2 # 這里注意下，必須是 // 而不是 /，否則不會自動取整，在list中取非整數則會報錯。guess = list[mid]# 如果猜的數是對了，返回結果if guess == item:return mid# 如果猜的數大了，上限減1if guess > item:high = mid - 1# 如果猜的數小了，下限加1else:low = mid + 1# 如果沒有這個元素，返回Nonereturn Nonemy_list = [1, 3, 5, 7, 9] ##測試數據

1.3大$O$表示法

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

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

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

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

1.4 小結

• 二分查找的速度比簡單查找要快許多，數據越大，差距就越明顯。
• $O(\log n)$比$O(n)$快。需要搜索的元素越多，前者比后者就快得越多。
• 算法運行時間并不以秒為單位。
• 算法運行時間是從其增速的角度來度量的。
• 算法運行時間用大$O$表示法表示。

練習

習題1.1

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

${\log }_{2}128=7步$

習題1.2

• 上面列表的長度翻倍后，最多需要幾步？

${\log }_{2}256=8步$

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

習題1.3

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

二分查找，為$O({\log }_{2}n)$。

習題1.4

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

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

習題1.5

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

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

習題1.6

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

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

總結

以上是生活随笔為你收集整理的算法图解第一章笔记与习题（算法简介）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。