“Grokking Algorithms: An illustrated guide for programmers and other curious people” — Aditya Y. Bhargava

Grokking 美国俚语，表示心领神会

  • understand (sth) intuitively or be empathy

    1. 二分查找

    对于有序序列，查找某一已知值时，可采用二分查找（从中间切开）的方法，每次排除一半的可能性，最多需要 [C1][查找] 二分查找与BigO - 图1 步（而简单查找需要n步）

对数运算，是幂运算的逆运算，本质上是指将多少个底数相乘可得到log后面的值

举例：

  • 查找100个元素，需要log2(100) = 6.6 -> 最多7次，最少6次后，能够定位目标元素位置
    1. def binary_search(l, num):
    2.   n = len(l)
    3.   low = 0
    4.   high = n - 1
    5.   while low <= high:
    6.       mid = (low + high) // 2
    7.       guess = l[mid]
    8.       if guess == num:
    9.           return mid
    10.       elif guess > num:
    11.           high = mid - 1
    12.       else:
    13.           low = mid + 1
    14.   return None

2. BigO 大O表示法

表示算法的速度有多快

  • 指出了算法运行时间的增速：即随着输入的增加，其运行时间将以什么样的速度增加
  • 通常是指最糟糕的情况（通常我们需要考虑平均情况）

举例1：

  • 普通查找：O(n)，随着计算元素的增加，时间线性增长
  • 二分查找：O(logn)，随着操作数增加，时间增长速度比线性增长慢的多
    • e.g. 根据名称查找电话号码：根据二分查找，名称有序列表

举例2：
在一张A4纸上画格子

  • 普通方法，一个一个画：O(n)
  • 将纸连续对折，每次操作使已有格子翻倍增加：O(logn)

2.1 常见BigO运行时间

  • 对数时间：O(logN)，二分查找
  • 线性时间：O(N)，简单查找
  • O(NlogN)，快速排序算法
  • O(N^2)，选择排序算法
  • O(N!)，旅行商问题

旅行商问题
一个旅行商需要前往5个城市，共有120种排列方式，如果去更多城市n，排列方式有n！个