《算法图解》读书笔记第一章算法简介

引言

算法是一组完成任务的指令，任何代码片段都可视为算法。

如果不明白各算法的优缺点，代码实现将毫无用处。

大O表示法

大O表示法指出了算法的速度有多快。例如列表包含n个元素，简单查找需要检查每个元素，因此需要执行n次操作，运行时间用大O表示法表示为O(n)。

大O表示法指的并非以秒为单位的速度，而是以操作数为单位，它可以指出算法运行时间的增速。

大O表示法说的是最糟的情形。所以简单查找的运行时间是O(n)而不是O(1)。

下面按从快到慢的顺序列出了经常会遇到的5种大O运行时间：

O (log n )，也叫对数时间，这样的算法包括二分查找。
O (n )，也叫线性时间，这样的算法包括简单查找。
O (n * log n )，这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。
O (n ² )，这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。
O (n !)，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。

下面是各个大O运行时间随着输入列表长度变化的趋势：

二分查找

二分查找是一种算法，其输入是一个有序的元素列表。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回null。比如在1-100中猜一个数字，我们先猜50，如果大了猜25，小了猜75，以此类推，这就是二分查找。

一般而言，对于包含n个元素的列表，用二分查找最多需要log₂n步，而简单查找最多需要n步。

一般而言，应选择效率最高的算法，以最大限度地减少运行时间或占用空间。

二分查找的python实现：

def binary_search(list, item):
    low, high = 0, len(list)-1
    while low <= high:
        mid = (low+high)//2
        guess = list[mid]
        if item == guess:
            return mid
        if item > guess:
            low = mid + 1
        else:
            high = mid - 1

my_list = [1, 3, 5, 7, 9]
print(binary_search(my_list, 3))  # => 1
print(binary_search(my_list, -1))  # => None

小结

二分查找的速度比简单查找快得多。
O(log n)比O(n)快。需要搜索的元素越多，前者比后者就快得越多。
算法运行时间并不以秒为单位，而是操作数。
算法运行时间是从其增速的角度度量的。
算法运行时间用大O表示法表示。