算法图解 (一)

第一章 算法简介

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

二分查找

二分搜索，也称折半搜索、对数搜索，是一种在有序数组中查找某一特定元素的搜素算法。
利用二分查找，猜想 1-100中的一个数字，7 次之内都能猜到

1.png
假设你要在字典中查找一个单词，而该字典包含 240000单词，只需要 18步 ！
2.png
对于包含 n 个元素的列表，用二分查找最多需要 log₂n，而简单查找最多需要 n 步。
PS: 二分查找只在有序的数组中有效
实例

给定一个有序（非降序）数组A，可含有重复元素，求最小的i使得A[i]等于target，不存在则返回-1。
时间复杂度要求为：O(log₂n)

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

if __name__ == '__main__':
    li = [1, 3, 5, 7, 9]
    print(binarySearch(li, 3))   # 1
    print(binarySearch(li, 10)) # -1

大 O 表示法

"大O记法": 对于单调的整数函数 f，如果存在一个整数函数 g 和实常数 c>0，使得对于充分大的 n 总有 f(n)<=c*g(n)，就说函数 g 是 f 的一个渐进函数 (忽略常数)，记为 f(n) = O(g(n))。也就是说，在趋向无穷的极限意义下，函数 f 的增长速度受到函数 g 的约束，即函数 f 与 函数 g 的特征相似。

时间复杂度: 假设存在函数 g，使得算法 A 处理规模为 n 的问题示例所用时间为 T(n) = O(g(n))，则称 O(g(n)) 为算法 A 的渐进时间复杂度，简称时间复杂度，记为 T(n)。 一般考虑的都是最坏时间复杂度

这些理论的东西看看就好，知道有这么个东西就可以了

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

• O(logn)，也叫对数时间，这样的算法包括二分查找；
• O(n)，也叫线性时间，这样的算法包括简单查找；
• O(n*logn)，这样的算法包括快速排序 ---- 一种较快的排序算法
• O(n²)，这样的算法包括选择排序 ---- 一种较慢的排序算法
• O(n!)，这样的算法包括文中讲到的旅行商问题的解决方案

常见复杂度之间的关系: 3.png

练习

使用大 O 表示法给出下述各种情形的运行时间。

1. 在电话薄中根据名字查找号码。(个人觉得应该是有序的) O(log₂n)
2. 在电话薄根据电话号码找人(提示: 你必须查找整个电话薄) O(n)
3. 阅读电话薄每个人的电话号码。 O(n)
4. 阅读电话薄中姓名以 A 打头的人的电话号码。O(n)

小结

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