算法图解 第一章

1. 引言

• 算法：算法是一组完成任务的指令。

2. 二分查找

• 二分查找适用于有序列表，时间复杂度为O(logn)

def binary_search(order_list, item):
    low = 0
    high = len(order_list) - 1

    while low <= high:
        mid = int((low + high) / 2)
        guess = order_list[mid]
        if guess == item:
            return mid
        if guess < item:
            low = mid + 1
        else:
            high = mid - 1
    return None

3. 大O表示法

• 算法的运行时间用大O表示法表示。

• 大O表示法是一种特殊的表示法，指出了算法的速度有多快。

• 大O表示法让你能够比较操作数，它指出了算法运行时间的增速。

• 大O表示法指出了最糟情况下的运行时间

• 算法的速度指的并非时间，而是操作数的增速。

• 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。

• O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快得越多。

常见大O运行时间

• O(log n)，也叫对数时间，这样的算法包括二分查找。

• O(n)，也叫线性时间，这样的算法包括简单查找。

• O(n* log n)，这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。

• O(n2)，这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。

• O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。