算法-第一章

---

算法

算法简介

算法是一组完成任务的指令。任何代码都可以叫做算法

二分查找

二分查找时一种算法，其输入是一个有序的元素列表

次数

1到100的数字集，只需要7步就可以找到正确的数值

一般而言，对于包含n个元素的列表，用二分查找最多需：
$$
log2n
$$

python实现

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

运行时间

简单查询(线性时间)：O(n)

二分查找(对数时间)：O(log2n)

大O表示法

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

表示的是最糟糕情况下的时间

除最糟糕情况下的运行时间外，还应该考虑平均情况的运行时间，这是很重要的

大O表示法并不考虑乘以，除以，加上，减去的数字

常见的五种大O运行时间：

O(log2n)  对数时间  二分查找

O(n)  线性时间，简单查找

O(n*log2n)  快速排序

O(n^2)  一种速度较慢的排序方法

O(n!)  旅行商问题

小结

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

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

算法的时间并不以秒为单位

---