《算法图解》阅读笔记

前言

• 问题解决技巧：分而治之 / 动态规划；贪婪算法
• 书目：Grokking algorithms: an illustrated guide for programmers and other curious people
• 中文名称：《算法图解——像小说一样有趣的算法入门书》

1 算法简介

• 二分查找：输入是一个有序的元素列表
• 运行时间：线性时间；对数时间
• 大O表示法：算法有多快，指出了算法需要执行的操作数，指出了最糟情况下的运行时间
  • O(log n)
  • O(n)
  • O(n * log n)
  • O(n 2 )
  • O(n!)

2 选择排序

• 数组和链表
  • 链表中的元素可存储在内存的任何地方。链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。
  • 数组的读取速度更快，支持随机访问，数组的元素都在一起。
• 数组的读取速度很快。
• 链表的插入和删除速度很快。

3 递归

• 递归只是让解决方案更清晰，并没有性能上的优势。实际上，在有些情况下，使用循环的性能更好。
• 基线条件（base case）和递归条件（recursive case）。递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己，从而避免形成无限循环。
• 调用栈：栈有两种操作：压入和弹出。
• 调用栈可能很长，这将占用大量的内存。
• 调用另一个函数时，当前函数暂停并处于未完成状态。该函数的所有变量的值都还在内存中。

4 快速排序

• 分而治之（divide and conquer，D&C）

  (1) 找出基线条件，这种条件必须尽可能简单。
  (2) 不断将问题分解（或者说缩小规模），直到符合基线条件。

• 编写涉及数组的递归函数时，基线条件通常是数组为空或只包含一个元素。

• 平均情况和最糟情况

5 散列表

• 散列函数是这样的函数，即无论你给它什么数据，它都还你一个数字。将输入映射到数字
• 散列表（hash table）——字典
• 避免冲突，需要有：
  • 较低的填装因子；
  • 良好的散列函数。

6 广度优先搜索

• 图模拟一组连接。
• 图由节点（node）和边（edge）组成。
• 队列：队列是一种先进先出（First In First Out，FIFO）的数据结构，而栈是一种后进先出（Last In First Out，LIFO）的数据结构。
• from collections import deque
• 你需要按加入顺序检查搜索列表中的人，否则找到的就不是最短路径，因此搜索列表必须是队列。
• 对于检查过的人，务必不要再去检查，否则可能导致无限循环。

7 狄克斯特拉算法

• Dijkstra’s algorithm，总权重最小的路径。
• 带权重的图称为加权图（weighted graph），不带权重的图称为非加权图（unweighted graph）。
• 狄克斯特拉算法只适用于有向无环图（directed acyclic
  graph，DAG）。
• 如果有负权边，就不能使用狄克斯特拉算法。
• 贝尔曼-福德算法（Bellman-Ford algorithm）。
• infinity = float(“inf”)

8 贪婪算法

• 每步都选择局部最优解；
• 教室调度问题；背包问题；集合覆盖问题；旅行商问题
• 很多非常聪明的人都认为，根本不可能编写出可快速解决这些问题的算法。NP-complete
• 没办法判断问题是不是NP完全问题：
  • 元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。
  • 如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题。
  • 如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题。

9 动态规划

• 动态规划先解决子问题，再逐步解决大问题。
• 在背包问题中，你必须在背包容量给定的情况下，偷到价值最高的商品。
• 在问题可分解为彼此独立且离散的子问题时，就可使用动态规划来解决。
• 每种动态规划解决方案都涉及网格。单元格中的值通常就是你要优化的值。
• 费曼算法（Feynman algorithm）
  • (1) 将问题写下来。
  • (2) 好好思考。
  • (3) 将答案写下来。
• 每个单元格都是一个子问题，因此你需要考虑如何将问题分解为子问题。
• 没有放之四海皆准的计算动态规划解决方案的公式。

10 K最近邻算法

• KNN用于分类和回归，需要考虑最近的邻居。
• 分类就是编组。
• 回归就是预测结果（如数字）。

11 10种算法

• 树：二叉查找树（binary search tree）；左子节点的值都比它小，而右子节点的值都比它大。
• 反向索引：