由二分查找算法学习算法的时间复杂度

二分查找

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

数据

• 函数形参：列表：xlist，要查找的值：item
• 查找范围的索引：low ~ high
• 要去的索引：mid，猜测的值：guess

算法

• 跟踪要查找的列表部分——开始时为整个列表
• 每次都检查中间的元素xlist[mid]
• 如果猜的数字小了，就相应地修改low,
• 如果猜的数字大了，就修改high，
• 猜对了返回mid，否则列表xlist里没有要查找的值iem，返回None

函数代码

def binsearch(xlist, y): #注意list不能直接做形参
    low = 0
    high = len(xlist) - 1
    while low <= high:
        mid = (low + high) / 2
        mid = round(mid)  #一定要取整
        guess = xlist[mid]
        if guess == y:
            return mid
        if guess > y:
            high = mid - 1
        else:
            low = mid + 1
    return 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$O表示法括号里面指出了最糟情况下的运行时间。

一些常见的大 $O$O 运行时间

$O(log n)$O(logn)，也叫对数时间，这样的算法包括二分查找。
$O(n)$O(n)，也叫线性时间，这样的算法包括简单查找。
$O(n * log n)$O(n∗logn)，这样的算法包括快速排序——一种速度较快的排序算法。
$O(n2)$O(n2)，这样的算法包括选择排序——一种速度较慢的排序算法。
$O(n!)$O(n!)，这样的算法包括旅行商问题的解决方案——一种非常慢的算法
还有其他的运行时间，但这5种是最常见的。
这里做了简化，实际上，并不能如此干净利索地将大$O$O运行时间转换为操作数，但就目前而言，这种准确度足够了。

启示：

• 算法的速度指的并非时间，而是操作数的增速。
• 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。
• 算法的运行时间用大O表示法表示。
• $O(log n)$O(logn)比$O(n)$O(n)快，当需要搜索的元素越多时，前者比后者快得越多