【学习】《算法图解》第一章学习笔记：算法简介与二分查找

前言

《算法图解》是一本入门算法的优秀读物，以图文并茂的方式讲解了各种基础算法。笔者最近在学习此书，特此记录学习笔记。本篇笔记主要记录第一章的核心内容，包括什么是算法、二分查找的思想及其实现、以及衡量算法效率的大O表示法。

一、什么是算法

算法（Algorithm）是一组用于完成特定任务的指令。简单来说，就是解决问题的方法和步骤。一个好的算法，不仅要能够正确解决问题，还要追求更高的效率，即用更少的时间和更少的内存。

二、二分查找

二分查找（Binary Search）是一种高效的查找算法，但它有一个重要的前提：输入的数据必须是有序的。

（一）算法原理

二分查找的原理非常简单。想象一下在电话簿里找一个名字，或者在字典里查一个单词。我们通常不会从第一页开始逐个查找，而是会：

  1. 打开书大约中间的一页。
  2. 比较中间的条目与我们要查找的目标。
  3. 如果目标条目在当前条目的前面，则在书的前半部分重复此过程。
  4. 如果目标条目在当前条目的后面，则在书的后半部分重复此过程。
  5. 重复以上步骤，直到找到目标或确定目标不存在。

这个过程就是二分查找。每次查找都将搜索范围缩小一半，因此效率很高。

例如，在一个包含 100 个有序元素的列表中查找一个元素，二分查找最多只需要 ( \lceil \log_2 100 \rceil = 7 ) 次比较。而如果使用简单查找（逐个比较），最坏情况下需要比较 100 次。

（二）Python代码示例

下面是《算法图解》中提供的二分查找的 Python 代码示例：

def binary_search(list, item):
  low = 0  # low 和 high 用于跟踪要在其中查找的列表部分
  high = len(list) - 1

  while low <= high:  # 只要范围没有缩小到只包含一个元素
    mid = (low + high) // 2  # 检查中间的元素
    guess = 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]
print(binary_search(my_list, 3))  # 输出: 1 (元素3的索引)
print(binary_search(my_list, -1)) # 输出: None (元素-1不存在)

（三）运行时间

对于包含 ( n ) 个元素的列表：

  • 简单查找 最多需要 ( n ) 步。
  • 二分查找 最多需要 ( \log_2 n ) 步。

这里的 ( \log ) 通常指以 2 为底的对数。当列表非常大时，二分查找的优势会非常明显。

三、大O表示法

大O表示法（Big O Notation）是一种特殊的表示法，用于描述算法的运行时间或空间复杂度的增速。它并不表示算法运行的具体时间（比如秒或毫秒），而是表示当输入规模 ( n ) 增大时，算法所需操作数量的增长趋势。

（一）算法的增长速度

不同的算法在处理相同规模的数据时，其操作次数的增长速度可能完全不同。大O表示法帮助我们比较这些增长速度，从而判断哪个算法在规模变大时表现更优。

例如，二分查找的运行时间是 ( O(\log n) )，简单查找的运行时间是 ( O(n) )。这意味着当列表长度增加时，二分查找的运行时间增长非常缓慢，而简单查找的运行时间则与列表长度成正比增长。

（二）常见的大O运行时间

以下是一些常见的大O运行时间，从快到慢排列：

  1. ( O(\log n) )，对数时间：例如二分查找。这类算法的性能非常好，即使数据规模很大，运行时间增长也很慢。
  2. ( O(n) )，线性时间：例如简单查找。这类算法的运行时间与输入数据的规模成正比。
  3. ( O(n \log n) )：例如快速排序、归并排序等高效的排序算法。
  4. ( O(n^2) )，平方时间：例如选择排序、冒泡排序等简单的排序算法。当数据规模增大时，运行时间会急剧增加。
  5. ( O(n!) )，阶乘时间：例如旅行商问题的某些暴力解法。这类算法的运行时间增长极快，通常只适用于解决非常小规模的问题。

（三）要点总结

  • 算法的速度指的并非具体时间，而是操作数的增速。
  • 讨论算法的速度时，我们关注的是随着输入规模的增加，其运行时间如何增长。
  • 算法的运行时间用大O表示法表示。
  • 大O表示法通常表示的是最坏情况下的运行时间。
  • ( O(\log n) ) 比 ( O(n) ) 快得多，特别是在处理大量数据时。

四、总结

《算法图解》的第一章为我们打开了算法世界的大门。通过二分查找的例子，我们不仅学习了一个实用的查找算法，更重要的是理解了衡量算法效率的核心概念——大O表示法。这为后续学习更复杂的算法和数据结构奠定了坚实的基础。

五、参考资料