文章目錄

• 二分查找
• • 數據
  • 算法
  • 函數代碼
  • 調用函數
• 大$O$表示法表示算法運行速度
• • 一些常見的大 $O$ 運行時間
  • 啟示：

二分查找

二分查找是一種算法，其輸入是一個有序的元素列表和要查找的元素。如果要查找的元素包含在列表中，二分查找返回其位置；否則返回null。

數據

• 函數形參：列表：xlist，要查找的值：item
• 查找范圍的索引：low ~ high
• 要去的索引：mid，猜測的值：guess

算法

• 跟蹤要查找的列表部分——開始時為整個列表
• 每次都檢查中間的元素xlist[mid]
• 如果猜的數字小了，就相應地修改low,
• 如果猜的數字大了，就修改high，
• 猜對了返回mid，否則列表xlist里沒有要查找的值iem，返回None

函數代碼

def binsearch(xlist, y): #注意list不能直接做形參low = 0high = len(xlist) - 1while low <= high:mid = (low + high) / 2mid = round(mid) #一定要取整guess = xlist[mid]if guess == y:return midif guess > y:high = mid - 1else:low = mid + 1return None

調用函數

import sys sys.path.append(r"D:\python\code") import binsearch x = list(range(10,110)) #創建順序數字列表 index = binsearch.binsearch(x, 100) print(index)

大$O$表示法表示算法運行速度

僅知道算法需要多長時間才能運行完畢還不夠，還需知道運行時間如何隨列表增長而增加。這正是大$O$表示法的用武之地。
大$O$表示法括號里面指出了最糟情況下的運行時間。

一些常見的大 $O$ 運行時間

$O(logn)$，也叫對數時間，這樣的算法包括二分查找。
$O(n)$，也叫線性時間，這樣的算法包括簡單查找。
$O(n?logn)$，這樣的算法包括快速排序——一種速度較快的排序算法。
$O(n^2)$，這樣的算法包括選擇排序——一種速度較慢的排序算法。
$O(n!)$，這樣的算法包括旅行商問題的解決方案——一種非常慢的算法
還有其他的運行時間，但這5種是最常見的。
這里做了簡化，實際上，并不能如此干凈利索地將大$O$運行時間轉換為操作數，但就目前而言，這種準確度足夠了。

啟示：

• 算法的速度指的并非時間，而是操作數的增速。
• 談論算法的速度時，我們說的是隨著輸入的增加，其運行時間將以什么樣的速度增加。
• 算法的運行時間用大O表示法表示。
• $O(logn)$比$O(n)$快，當需要搜索的元素越多時，前者比后者快得越多

總結

以上是生活随笔為你收集整理的由二分查找算法学习算法的时间复杂度的全部內容，希望文章能夠幫你解決所遇到的問題。

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