算法简介

[qingquan-li]

• 本文内容摘录或参考自《算法图解》

一、算法是什么

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

算法应用场景：使用图算法编写跟踪用户的AI系统；GPS设备使用图算法来计算前往目的地的最短路径；使用K最近邻算法编写推荐系统；使用动态规划来编写下国际跳棋的AI算法。

二、二分查找

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

使用简单查找法查找列表中的元素时，在最糟情况下需要查看每个元素。因此，如果列表包含8个数字，你最多需要检查8个数字。

而使用二分查找时，最多需要检查 log n 个元素（这里的 log 指的都是 log₂ ）。如果列表包含8个元素，你最多需要检查3个元素，因为 log 8 = 3（2³ = 8）。如果列表包含1024个元素，你最多需要检查10个元素， 因为log 1024 = 10（2¹⁰ =1024）。

编写执行二分查找的Python代码：

参考：https://github.com/egonSchiele/grokking_algorithms/blob/master/01_introduction_to_algorithms/python/

def binary_search(list, item):
    """二分查找"""
    # low和high用于跟踪要在其中查找的列表部分
    low = 0
    high = len(list) - 1
    # 只要列表范围没有缩小到只包含一个元素，就检查中间的元素
    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]  # 猜测数字值为列表中第list[mid]个
        if guess == item:  # 猜对了，即查找到元素了
            return mid
        if guess > item:  # 猜大了
            high = mid - 1
        else:  # 猜小了
            low = mid + 1
    return None  # 在列表中查找不到指定的元素（数字）

my_list = [1, 3, 5, 7, 9]
position = binary_search(my_list, 3)
print(position)  # 打印出1

三、大O表示法

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

例如，假设列表包含n个元素。简单查找需要检查每个元素，因此需要执行n次操作。使用大O表示法，这个运行时间为O(n) 。

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

按从快到慢的顺序列出常见的5种大O运行时间：

1. O(log n) 也叫对数时间，这样的算法包括二分查找
2. O(n) 也叫线性时间，这样的算法包括简单查找
3. O(n * log n) 这样的算法包括快速排序（一种速度较快的排序算法）
4. O(n2) 这样的算法包括选择排序（一种速度较慢的排序算法）
5. O(n!) 这样的算法包括旅行商问题的解决方案（一种非常慢的算法）

总结：

• 算法的运行时间用大O表示法表示：O(n) （n为操作数）。 算法的速度指的并非时间，而是操作数的增速。

• 算法运行时间并不以秒为单位，算法运行时间是从其增速的角度度量的。 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。

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

附：旅行商问题：

有一位旅行商。 他需要前往5个城市，同时要确保旅程最短。

对于每种顺序，他都计算总旅程，再挑选出旅程最短的路线。5个城市有120种不同的排列方式（5的阶乘为1×2×3×4×5=120）。因此，在涉及5个城市时，解决这个问题需要执行120次操作。涉及6个城市时，需要执行720 次操作（有720种不同的排列方式）。涉及7个城市时，需要执行5040次操作！

推而广之，涉及 n 个城市时，需要执行 n!（n的阶乘）次操作才能计算出结果。因此运行时间为 O(n!) ，即阶乘时间。