概述

算法复杂度 / Big-O / 渐进分析法 ✅

• 这里没有什么需要实施的，你只是在观看视频并记笔记！耶！
• 这里有很多视频，只要看到你理解为止就好了，你随时可以回来复习。
• 如果你不理解背后的所有数学，不要担心。
• 你只需要理解如何用大O表示法来表达算法的复杂度。

---

• 哈佛大学CS50 - 渐进符号（视频）
• 大O符号（通用快速教程）（视频）
• 大O符号（以及Ω和Θ）- 最佳数学解释（视频）
• Skiena（视频）
• 加州大学伯克利分校关于大O符号（视频）
• 摊还分析（视频）
• TopCoder（包括递归关系和主定理）：
  • 计算复杂性：第1部分
  • 计算复杂性：第2部分
• 速查表
• [回顾] 在 18 分钟内分析算法（播放列表）（视频）

好吧，差不多就到这里了。

当你阅读《破解编程面试》时，有一个章节专门讲述此事，并在最后进行了一次测验，以测试你是否能够确定不同算法的运行时间复杂度。这是一个非常全面的复习和测试。

数据结构

• 数组（Arrays） ✅

  • 介绍：
    • 数组 CS50 哈佛大学
    • 数组（视频）
    • 加州大学伯克利分校CS61B - 线性和多维数组（视频）（从15分32秒开始）
    • 动态数组（视频）
    • 嵌套数组（视频）
  • 实现一个动态数组（可自动调整大小的可变数组）：
    • 练习使用数组和指针去编码，并且指针是通过计算去跳转而不是使用索引
    • 通过分配内存来新建一个原生数据型数组
      • 可以使用 int 类型的数组，但不能使用其语法特性
      • 从大小为16或更大的数（使用2的倍数 —— 16、32、64、128）开始编写
    • size() —— 数组元素的个数
    • capacity() —— 可容纳元素的个数
    • is_empty()
    • at(index) —— 返回对应索引的元素，且若索引越界则愤然报错
    • push(item)
    • insert(index, item) —— 在指定索引中插入元素，并把后面的元素依次后移
    • prepend(item) —— 可以使用上面的 insert 函数，传参 index 为 0
    • pop() —— 删除在数组末端的元素，并返回其值
    • delete(index) —— 删除指定索引的元素，并把后面的元素依次前移
    • remove(item) —— 删除指定值的元素，并返回其索引（即使有多个元素）
    • find(item) —— 寻找指定值的元素并返回其中第一个出现的元素其索引，若未找到则返回 -1
    • resize(new_capacity) // 私有函数
      • 若数组的大小到达其容积，则变大一倍
      • 获取元素后，若数组大小为其容积的1/4，则缩小一半
  • 时间复杂度
    • 在数组末端增加/删除、定位、更新元素，只允许占 O(1) 的时间复杂度（平摊（amortized）去分配内存以获取更多空间）
    • 在数组任何地方插入/移除元素，只允许 O(n) 的时间复杂度
  • 空间复杂度
    • 因为在内存中分配的空间邻近，所以有助于提高性能
    • 空间需求 = （大于或等于 n 的数组容积）* 元素的大小。即便空间需求为 2n，其空间复杂度仍然是 O(n)

• 链表（Linked Lists）

  • 介绍：
    • 链表 CS50 哈佛大学 - 这样建立了直观感。
    • 单链表（视频）
    • CS 61B - 链表1（视频）
    • CS 61B - 链表 2（视频）
    • [复习] 4分钟了解链表（视频）
  • C代码（视频）
    • 不是整个视频，只是关于Node结构和内存分配的部分。
  • 链表 vs 数组：
    • 核心链表与数组（视频）
    • 在现实世界中，链表与数组的比较（视频）
  • 为什么你需要避免使用链表（视频）
  • 的确：你需要关于“指向指针的指针”的相关知识：（因为当你传递一个指针到一个函数时，
    该函数可能会改变指针所指向的地址）该页只是为了让你了解“指向指针的指针”这一概念。
    但我并不推荐这种链式遍历的风格。因为，这种风格的代码，其可读性和可维护性太低。
    • 指向指针的指针
  • 实现（我实现了使用尾指针以及没有使用尾指针这两种情况）：
    • size() —— 返回链表中数据元素的个数
    • empty() —— 若链表为空则返回一个布尔值 true
    • value_at(index) —— 返回第 n 个元素的值（从0开始计算）
    • push_front(value) —— 添加元素到链表的首部
    • pop_front() —— 删除首部元素并返回其值
    • push_back(value) —— 添加元素到链表的尾部
    • pop_back() —— 删除尾部元素并返回其值
    • front() —— 返回首部元素的值
    • back() —— 返回尾部元素的值
    • insert(index, value) —— 插入值到指定的索引，并把当前索引的元素指向到新的元素
    • erase(index) —— 删除指定索引的节点
    • value_n_from_end(n) —— 返回倒数第 n 个节点的值
    • reverse() —— 逆序链表
    • remove_value(value) —— 删除链表中指定值的第一个元素
  • 双向链表
    • 介绍（视频）
    • 并不需要实现

• 堆栈（Stack）

  • 堆栈（视频）
  • [Review] Stacks in 3 minutes (video)
  • 可以不实现，因为使用数组来实现是微不足道的事

• 队列（Queue）

  • 队列（视频）
  • 原型队列/先进先出（FIFO）
  • [Review] Queues in 3 minutes (video)
  • 使用含有尾部指针的链表来实现:
    • enqueue(value) —— 在尾部添加值
    • dequeue() —— 删除最早添加的元素并返回其值（首部元素）
    • empty()
  • 使用固定大小的数组实现：
    • enqueue(value) —— 在可容的情况下添加元素到尾部
    • dequeue() —— 删除最早添加的元素并返回其值
    • empty()
    • full()
  • 花销：
    • 在糟糕的实现情况下，使用链表所实现的队列，其入列和出列的时间复杂度将会是 O(n)。
      因为，你需要找到下一个元素，以致循环整个队列
    • enqueue：O(1)（平摊（amortized）、链表和数组 [探测（probing）]）
    • dequeue：O(1)（链表和数组）
    • empty：O(1)（链表和数组）

• 哈希表（Hash table）

  • 视频：

    • 链式哈希表（视频）
    • Table Doubling 和 Karp-Rabin（视频）
    • Open Addressing 和密码型哈希（Cryptographic Hashing）（视频）
    • PyCon 2010：强大的字典（视频）
    • PyCon 2017：字典更强大（视频）
    • (高级) 随机化：通用和完美哈希（视频）
    • (进阶)完美哈希（Perfect hashing）（视频）
    • [复习]4分钟了解哈希表（视频）

  • 在线课程：

    • 核心哈希表（视频）
    • 数据结构（视频）
    • 电话簿问题（视频）
    • 分布式哈希表：
      • Dropbox中的即时上传和存储优化（视频）
      • 分布式哈希表（视频）

  • 使用线性探测法的数组实现

    • hash(k, m) - m是哈希表的大小
    • add(key, value) - 如果键已存在，则更新值
    • exists(key) - 检查键是否存在
    • get(key) - 获取给定键的值
    • remove(key) - 删除给定键的值

更多的知识

• 二分查找（Binary search）

  • 二分查找（视频）
  • 二分查找（视频）
  • 详情
  • 蓝图
  • 【复习】四分钟二分查找(视频)
  • 实现：
    • 二分查找（在一个已排序好的整型数组中查找）
    • 迭代式二分查找

• 按位运算（Bitwise operations）

  • Bits 速查表 ── 你需要知道大量2的幂数值（从2^1 到 2^16 及 2^32）
  • 好好理解位操作符的含义：&、|、^、~、>>、<<
    • 字码（words）
    • 好的介绍：
      位操作（视频）
    • C 语言编程教程 2-10：按位运算（视频）
    • 位操作
    • 按位运算
    • Bithacks
    • 位元抚弄者（The Bit Twiddler）
    • 交互式位元抚弄者（The Bit Twiddler Interactive）
    • 位操作技巧（Bit Hacks）（视频）
    • 练习位操作
  • 一补数和补码
    • 二进制：利 & 弊（为什么我们要使用补码）（视频）
    • 一补数（1s Complement）
    • 补码（2s Complement）
  • 计算置位（Set Bits）
    • 计算一个字节中置位（Set Bits）的四种方式（视频）
    • 计算比特位
    • 如何在一个 32 位的整型中计算置位（Set Bits）的数量
  • 交换值：
    • 交换（Swap）
  • 绝对值：
    • 绝对整型（Absolute Integer）

树（Trees）

• 树-介绍

  • 树的介绍（视频）
  • 树遍历（视频）
  • BFS（广度优先搜索）和DFS（深度优先搜索）（视频）
    • BFS 笔记
      • 层次遍历（BFS，使用队列）
      • 时间复杂度： O(n)
      • 空间复杂度：最佳情况：O(1)，最坏情况：O(n/2)=O(n)
    • DFS 笔记：
      • 时间复杂度：O(n)
      • 空间复杂度：
        • 最好情况：O(log n) - 树的平均高度
        • 最坏情况：O(n)
      • 中序遍历（DFS：左、节点本身、右）
      • 后序遍历（DFS：左、右、节点本身）
      • 先序遍历（DFS：节点本身、左、右）
  • [复习]4分钟内的广度优先搜索（视频）
  • [复习] 4分钟内的深度优先搜索（视频）
  • [复习]11分钟内的树遍历（播放列表）（视频）

• 二叉查找树（Binary search trees）：BSTs

  • 二叉搜索树复习（视频）
  • 介绍（视频）
  • MIT（视频）
  • C/C++:
    • 二叉查找树 —— 在 C/C++ 中实现（视频）
    • BST 的实现 —— 在堆栈和堆中的内存分配（视频）
    • 在二叉查找树中找到最小和最大的元素（视频）
    • 寻找二叉树的高度（视频）
    • 二叉树的遍历 —— 广度优先和深度优先策略（视频）
    • 二叉树：层序遍历（视频）
    • 二叉树的遍历：先序、中序、后序（视频）
    • 判断一棵二叉树是否为二叉查找树（视频）
    • 从二叉查找树中删除一个节点（视频）
    • 二叉查找树中序遍历的后继者（视频）
  • 实现：
    • insert // 将值插入树中
    • get_node_count // 查找树上的节点数
    • print_values // 从小到大打印树中节点的值
    • delete_tree
    • is_in_tree // 如果值存在于树中则返回 true
    • get_height // 以节点为单位返回高度（单个节点的高度为1）
    • get_min // 返回树上的最小值
    • get_max // 返回树上的最大值
    • is_binary_search_tree
    • delete_value
    • get_successor // 返回给定值的后继者，若没有则返回-1

• 堆（Heap） / 优先级队列（Priority Queue） / 二叉堆（Binary Heap）

  • 以树形结构可视化，但通常在存储上是线性的（数组、链表）
  • 堆（Heap）
  • 堆简介（视频）
  • 二叉树（视频）
  • 树高度备注（视频）
  • 基本操作（视频）
  • 完全二叉树（视频）
  • 伪代码（视频）
  • 堆排序 - 跳转到开始部分（视频）
  • 堆排序（视频）
  • 构建堆（视频）
  • MIT：堆和堆排序（视频）
  • CS 61B Lecture 24：优先队列（视频）
  • 线性时间构建堆（大顶堆）
  • [复习] 13分钟了解堆（视频）
  • 实现一个大顶堆：
    • insert
    • sift_up —— 用于插入元素
    • get_max —— 返回最大值但不移除元素
    • get_size() —— 返回存储的元素数量
    • is_empty() —— 若堆为空则返回 true
    • extract_max —— 返回最大值并移除
    • sift_down —— 用于获取最大值元素
    • remove(i) —— 删除指定索引的元素
    • heapify —— 构建堆，用于堆排序
    • heap_sort() —— 拿到一个未排序的数组，然后使用大顶堆或者小顶堆进行就地排序

排序（Sorting）

• 笔记:
  • 实现各种排序，知道每种排序的最坏、最好和平均的复杂度分别是什么场景:
    • 不要用冒泡排序 - 效率太差 - 时间复杂度 $O(n^2)$, 除非 $n <= 16$
  • 排序算法的稳定性 ("快排是稳定的么?")
    • 排序算法的稳定性
    • 排序算法的稳定性
    • 排序算法的稳定性
    • 排序算法 - 稳定性
  • 哪种排序算法可以用链表？哪种用数组？哪种两者都可？
    • 并不推荐对一个链表排序，但归并排序是可行的.
    • 链表的归并排序

关于堆排序，请查看前文堆的数据结构部分。堆排序很强大，不过是非稳定排序。

• Sedgewick ── 归并排序（5个视频）
  • 1. 归并排序（Mergesort）
  • 2. 自底向上的归并排序（Bottom up Mergesort）
  • 3. 排序复杂性（Sorting Complexity）
  • 4. 比较器（Comparators）
  • 5. 稳定性（Stability）
• Sedgewick ── 快速排序（4个视频）
  • 1. 快速排序（Quicksort）
  • 2. 选择排序（Selection）
  • 3. 重复键（Duplicate Keys）
  • 4. 系统排序（System Sorts）
• 加州大学伯克利分校：
  • CS 61B Lecture 29：排序 I（视频）
  • CS 61B Lecture 30：排序 II（视频）
  • CS 61B Lecture 32：排序 III（视频）
  • CS 61B Lecture 33：排序 V（视频）
  • CS 61B 2014-04-21：基数排序（视频）
• 冒泡排序（视频）
• 冒泡排序分析（视频）
• 插入排序 & 归并排序（视频）
• 插入排序（视频）
• 归并排序（视频）
• 快排（视频）
• 选择排序（视频）
• 归并排序代码：
  • 使用外部数组（C语言）
  • 使用外部数组（Python语言）
  • 对原数组直接排序（C++）
• 快速排序代码：
  • 实现（C语言）
  • 实现（C语言）
  • 实现（Python语言）
• [Review] Sorting (playlist) in 18 minutes
  • Quick sort in 4 minutes (video)
  • Heap sort in 4 minutes (video)
  • Merge sort in 3 minutes (video)
  • Bubble sort in 2 minutes (video)
  • Selection sort in 3 minutes (video)
  • Insertion sort in 2 minutes (video)
• 实现:
  • 归并：平均和最差情况的时间复杂度为 $O(n \log n)$。
  • 快排：平均时间复杂度为 $O(n \log n)$。
  • 选择排序和插入排序的最坏、平均时间复杂度都是 $O(n^2)$。
  • 关于堆排序，请查看前文堆的数据结构部分。
• 有兴趣的话，还有一些补充，但并不是必须的:
  • Sedgewick──基数排序 (6个视频)
    • 1. Java 中的字符串
    • 2. 键值索引计数（Key Indexed Counting）
    • 3. Least Significant Digit First String Radix Sort
    • 4. Most Significant Digit First String Radix Sort
    • 5. 3中基数快速排序
    • 6. 后继数组（Suffix Arrays）
  • 基数排序
  • 基数排序（视频）
  • 基数排序, 计数排序 (线性时间内)（视频）
  • 随机算法: 矩阵相乘, 快排, Freivalds' 算法（视频）
  • 线性时间内的排序（视频）

总结一下，这是15种排序算法的可视化表示。
如果你需要有关此主题的更多详细信息，请参阅“一些主题的额外内容”中的“排序”部分。

图（Graphs）

图表可以用来表示计算机科学中的许多问题，所以这一部分很长，就像树和排序一样。

• 笔记:

  • 有4种基本方式在内存里表示一个图:
    • 对象和指针
    • 邻接矩阵
    • 邻接表
    • 邻接图
  • 熟悉以上每一种图的表示法，并了解各自的优缺点
  • 广度优先搜索和深度优先搜索：知道它们的计算复杂度和设计上的权衡以及如何用代码实现它们
  • 遇到一个问题时，首先尝试基于图的解决方案，如果没有再去尝试其他的。

• MIT（视频）：

  • 广度优先搜索
  • 深度优先搜索

• Skiena 教授的课程 - 很不错的介绍:

  • CSE373 2012 - 课程 11 - 图的数据结构（视频）
  • CSE373 2012 - 课程 12 - 广度优先搜索（视频）
  • CSE373 2012 - 课程 13 - 图的算法（视频）
  • CSE373 2012 - 课程 14 - 图的算法 (1)（视频）
  • CSE373 2012 - 课程 15 - 图的算法 (2)（视频）
  • CSE373 2012 - 课程 16 - 图的算法 (3)（视频）

• 图 (复习和其他):

  • 6.006 单源最短路径问题（视频）
  • 6.006 Dijkstra算法（视频）
  • 6.006 Bellman-Ford算法（视频）
  • 6.006 加速Dijkstra算法（视频）
  • Aduni：图算法 I - 拓扑排序，最小生成树，Prim算法 - 讲座6（视频）
  • Aduni：图算法 II - DFS，BFS，Kruskal算法，Union Find数据结构 - 讲座7（视频）
  • Aduni：图算法 III：最短路径 - 讲座8（视频）
  • Aduni：图算法 IV：几何算法入门 - 讲座9（视频）
  • CS 61B 2014：加权图（视频）
  • 贪婪算法：最小生成树（视频）
  • 强连通分量Kosaraju算法图算法（视频）
  • [复习] 最短路径算法（播放列表）16分钟（视频）
  • [复习] 最小生成树（播放列表）4分钟（视频）

• 完整的 Coursera 课程:

  • 图的算法（视频）

• 我会实现:

  • DFS 邻接表 (递归)
  • DFS 邻接表 (栈迭代)
  • DFS 邻接矩阵 (递归)
  • DFS 邻接矩阵 (栈迭代)
  • BFS 邻接表
  • BFS 邻接矩阵
  • 单源最短路径问题 (Dijkstra)
  • 最小生成树
  • 基于 DFS 的算法 (根据上文 Aduni 的视频):
    • 检查环 (我们会先检查是否有环存在以便做拓扑排序)
    • 拓扑排序
    • 计算图中的连通分支
    • 列出强连通分量
    • 检查双向图

更多知识

• 递归（Recursion）

  • Stanford 大学关于递归 & 回溯的课程:
    • 课程 8 | 抽象编程（视频）
    • 课程 9 | 抽象编程（视频）
    • 课程 10 | 抽象编程（视频）
    • 课程 11 | 抽象编程（视频）
  • 什么时候适合使用
  • 尾递归会更好么?
    • 什么是尾递归以及为什么它如此糟糕?
    • 尾递归（视频）
  • 解决任何递归问题的5个简单步骤（视频）

  回溯蓝图: Java
  Python

• 动态规划（Dynamic Programming）

  • 在你的面试中或许没有任何动态规划的问题，
    但能够知道一个题目可以使用动态规划来解决是很重要的。
  • 这一部分会有点困难，每个可以用动态规划解决的问题都必须先定义出递推关系，要推导出来可能会有点棘手。
  • 我建议先阅读和学习足够多的动态规划的例子，以便对解决 DP 问题的一般模式有个扎实的理解。
  • 视频:
    • Skiena：CSE373 2020 - 讲座19 - 动态规划简介（视频）
    • Skiena：CSE373 2020 - 讲座20 - 编辑距离（视频）
    • Skiena：CSE373 2020 - 讲座20 - 编辑距离（续）（视频）
    • Skiena：CSE373 2020 - 讲座21 - 动态规划（视频）
    • Skiena：CSE373 2020 - 讲座22 - 动态规划和复习（视频）
    • Simonson：动态规划 0（从59:18开始）（视频）
    • Simonson：动态规划 I - 第11讲（视频）
    • Simonson：动态规划 II - 第12讲（视频）
    • 单独的动态规划问题列表（每个都很短）:
      动态规划（视频）
  • 耶鲁课程笔记:
    • 动态规划
  • Coursera 课程:
    • RNA 二级结构问题（视频）
    • 动态规划算法（视频）
    • DP 算法描述（视频）
    • DP 算法的运行时间（视频）
    • DP vs 递归实现（视频）
    • 全局成对序列排列（视频）
    • 本地成对序列排列（视频）

• 组合（Combinatorics） (n 中选 k 个) & 概率（Probability）

  • 数据技巧: 如何找出阶乘、排列和组合(选择)（视频）
  • 来点学校的东西: 概率（视频）
  • 来点学校的东西: 概率和马尔可夫链（视频）
  • 可汗学院:
    • 课程设置:
      • 概率理论基础
    • 只有视频 - 41 (每一个都短小精悍):
      • 概率解释（视频）

• NP, NP-Completeness和近似算法

  • 知道最经典的一些 NP-Completeness 问题，比如旅行商问题和背包问题，
    而且能在面试官试图忽悠你的时候识别出他们。
  • 知道 NP-Completeness 是什么意思.
  • 计算复杂度（视频）
  • Simonson:
    • 贪心算法. II & 介绍 NP-Completeness（视频）
    • NP-Completeness II & 归约（视频）
    • NP-Completeness III（视频）
    • NP-Completeness IV（视频）
  • Skiena:
    • CSE373 2012 - 课程 23 - 介绍 NP-Completeness IV（视频）
    • CSE373 2012 - 课程 24 - NP-Completeness证明（视频）
    • CSE373 2012 - 课程 25 - NP-Completeness挑战（视频）
    • CSE373 2020年 - 第26讲 - NP-Completeness挑战（视频）
  • 复杂度: P, NP, NP-完全性, 规约（视频）
  • 复杂度: 近视算法 Algorithms（视频）
  • 复杂度: 固定参数算法（视频）
  • Peter Norvik 讨论旅行商问题的近似最优解:
    • Jupyter 笔记本
  • 《算法导论》（CLRS）的第 1048 - 1140 页。

其他

链表加数组实现自动扩容