Guiding Principles 是指在算法分析中遵循的一些基本原则，例如：

• 最坏情况分析：对于任意输入规模n，算法的运行时间都有一个上界。
• 渐进分析：忽略常数因子和低阶项，只关注输入规模很大时的运行时间。
• 大O符号：用来描述和比较算法运行时间的符号和方法，表示算法运行时间的一个上界。

Five Representative Problems

所有问题都可以归结为以下五类

• 区间调度：给定一组具有开始时间和结束时间的任务，找到最大的互相兼容（即任务不重叠）的子集。 $O(nlogn)$ Greedy 贪心
• • 加权区间调度：给定一组具有开始时间、结束时间和权重的任务，找到最大权重的互相兼容的子集。 $O(nlogn)$ Dynamic Programming
• • 二分匹配：给定一个二分图，找到最大的匹配。 $O(n^2)$ Network Flow——Max-flow and Ford-Fulkerson Algorithm
• • 独立集合：给定一个图，找到最大的独立集合（即没有两个节点相邻的子集）。 NP-complete
• • 竞争性设施位置：给定一个带有每个节点权重的图，两个竞争者轮流选择节点。不允许选择任何已经被选择或与已选择节点相邻的节点。目标是选择最大权重的节点子集。 PSPACE-complete

计算复杂性

Asymptotic Order of Growth 渐进阶数

Common Running Times

• 线性时间：O(n)。运行时间最多是输入规模n的某个常数倍。例如，计算n个数的最大值，或者合并两个有序的长度为n的数组。
• 对数时间：O(logn)。运行时间随着输入规模n的增长而呈现出较慢的速度。divide-and-conquer算法。例如，二分搜索或者快速幂。
• 平方时间：O(n^2)。运行时间是输入规模n的平方的某个常数倍。例如，枚举所有元素对，或者冒泡排序、插入排序、选择排序等。
• 立方时间：O(n^3)。运行时间是输入规模n的立方的某个常数倍。例如，枚举所有元素三元组，或者矩阵乘法、高斯消元等。
• 多项式时间：O(n^k)。运行时间是输入规模n的某个固定次数k的幂的某个常数倍。例如，枚举所有大小为k的子集，或者求解k个节点的独立集问题等。