← Back

Introduction to Algorithms 算法导论

重点

第一章 What is Algorithm

  1. 算法的概念
  2. 算法定义中的 5 个性质: 输入, 输出, 确定性, 有穷性, 有效性

第二章 算法设计与分析基础

  1. 如何做算法设计, 算法分析
    1. 基本思想
    2. 具体过程
    3. 伪代码
    4. 时空间复杂度
    5. 需要问题具有的性质
    6. 典型例子
  2. 复杂度不确定: 条件判断情况
  3. 最好情况, 平均情况, 最坏情况
  4. 递推表达式
  5. 归并排序

第三章 Asymptotic Notation & Analysis 渐进记号与渐进分析

  1. 渐进记号, 渐进分析: n 趋于无穷情况的复杂度 O,ΘO,\Theta
  2. f(x) = O(…) 其实表示”属于”
  3. 渐进记号写在左边和写在右边的区别 Asymptotic Notation Tips

第四章 递归表达式求解 & 分治策略

  1. 递归表达式的求解
    1. 递归树 Recursion Tree Method 递归树法
    2. 代入法 Substitution Method 代入法
    3. 主方法 Master Method 主方法
    4. 迭代展开法 Iterating the Recurrence 迭代展开法
  2. 分治策略
    1. 基本思想, 具体过程, 伪代码, 时空间复杂度
    2. 需要具有最优子结构
    3. 典型例子

第六章 Heap Sort 堆排序

第七章 Quick Sort 快速排序

  1. 为什么快速排序时间复杂度为 O(n²) 仍然可以称为”快速”

第八章 Linear Time Sort 线性时间排序

  1. 计数排序和基数排序重要, 桶排序了解
  2. 计数排序: 非线性时间的条件 Counting Sort 计数排序
  3. 基数排序: Radix Sort 基数排序
  4. 概念: 稳定排序, 置换排序

第九章 顺序统计

  1. 顺序统计的概念
  2. 同时找出最小值和最大值, 需要多少次比较
  3. 期望为线性时间的选择算法 Quick Select 快速选择
  4. 最坏情况为线性时间的选择算法 BFPRT - Median of Medians BFPRT选择算法

第十一章 散列表

  1. 散列函数如何设计
  2. Direct Access Table
  3. 开放地址法, 探查序列
  4. 全域散列 important
  5. 完美散列

第十二章 Binary Search Tree 二叉搜索树

  1. 所有二叉搜索树的操作时间复杂度为 O(log n)
  2. 前驱, 后继

第十三章 Red-Black Tree 红黑树

  1. 删除略作了解, 其他重要

第十四章 数据结构的扩张

  1. 基本步骤
    1. 选择基础数据结构
    2. 添加属性, 基于何种原则
    3. 基本操作如何维护新属性
    4. 根据新属性开发新算法解决实际问题

第十五章 Dynamic Programming 动态规划 important

  1. 基本思想
  2. 具体过程
  3. 伪代码
  4. 时空间复杂度
  5. 需要问题具有的性质: 最优子结构 && 重叠子问题
  6. 典型例子
  7. 自顶向下 || 自底向上

第十六章 Greedy Algorithm 贪心算法

  1. Minimum Spanning Tree 最小生成树
  2. Shortest Path 最短路径
    1. 什么情况不存在最短路径
    2. DJ 和 BF 的区别与联系
    3. 差分约束
  3. Activity Selection 活动选择问题

第二十六章 Network Flow 网络流

  1. 源与汇的概念
  2. 边的容量
  3. 流 <= 容量
  4. 流入 == 流出
  5. 割的概念: 割出来的两个集合, 其中一个包含源, 另一个包含汇
  6. 如何求最大流
    1. 找增广路径
      1. 引入残流图
      2. 给定一个网络, 如何画残流图
    2. Ford-Fulkerson Algorithm 福特福克森算法
      1. 割的容量
      2. 割的流量

解空间树

  1. Branch and Bound 分支限界法
  2. Backtracking 回溯法
  3. 什么是解空间树?

题型

判断题 (10 × 1 = 10 分)

  1. 插入排序在最坏情况的时间复杂度
  2. 堆排序是最优的比较排序算法
  3. Dijkstra 算法是一种贪心算法
  4. 任何基数排序算法都是线性时间算法

填空题 (10 × 1 = 10 分)

  1. 空间树常规分为哪两种树: 子集树, 排列树
  2. 回溯法
  3. DP 需要问题具备的性质
  4. 散列的方法: 开放地址法和直接寻址和
  5. 最少需要多少次比较

简答题 (4 × 5 = 20 分)

  1. 某种算法策略的基本思想, 解题步骤…
    1. 分治, DP, 贪心, …
    2. DP 解题步骤, 常见方法
  2. 什么是简单一次散列, 什么是完美散列…

计算题 (56 题 × 1012 分 = 60 分)

  1. 求解递归表达式
    1. 递归树
    2. 主方法
    3. 代入法
  2. 经典问题: MCM, LCS 等
    1. 分析
    2. 伪代码
    3. 时空间复杂度
    4. 递归表达式

知识点导航

Divide & Conquer 分治

Sorting Algorithms 排序算法

Order Statistic 顺序统计量

Hashing I 哈希

Binary Search Tree 二叉搜索树

Red-Black Tree 红黑树

Dynamic Programming 动态规划

Greedy Algorithm 贪心算法

Greedy 和 DP 都有最优子结构 (同); Greedy 是自顶向下, DP 可上可下 (异).

Network Flow 网络流

Backtracking 回溯法

Branch and Bound 分支限界法