算法和算法分析

复习定位

算法是解决问题的方法的步骤描述。同样的排序任务——冒泡排序和快速排序的理论执行时间的增长率完全不同。大O表示法用来描述算法运行时间随输入规模增长的增长趋势——不是运行的具体秒数。学会推导算法的时间复杂度(最坏/平均/最好)是算法设计的基本功。

算法的五个特性

一个有穷的指令序列必须满足：

• 有穷性：算法在有限步骤后必须结束——不能无限循环或无限递归。
• 确定性：每条指令的含义确切且唯一——没有二义性——相同输入必定产生相同输出。
• 可行性：每条指令都能通过已经实现的基本运算完成——不能执行未定义的操作。
• 输入：算法有0个或多个输入——来自指定的数据源。
• 输出：算法有1个或多个输出——与输入存在特定关系的运算结果。

时间复杂度分析

算法的时间开销用语句执行次数来度量——不依赖实际的CPU频率。计算基本语句执行次数与输入规模n的关系——取增长率的最高次项忽略低次项和常数——这就是大O表示法。

int sum = 0;         // 1次
for (int i = 0; i < n; i++)   // n+1次(判断包括最后一次评估)
    sum += i;        // n次

总执行次数=2n+2→O(n)。

两层嵌套循环：

for (int i = 0; i < n; i++)           // n+1次
    for (int j = 0; j < n; j++)       // n(n+1)次
        printf("%d", i + j);          // n²次

总次数≈2n²+2n+1→O(n²)。

常见的时间复杂度效率排序(增长由慢到快)：
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

O(2ⁿ)和O(n!)是不可接受的——指数增长迅速耗尽计算资源——当n=100时——2¹⁰⁰次运算现有最长服务器算不完在人类文明寿命之外。

空间复杂度

算法在运行过程中需要的额外内存空间(除了输入数据之外)。原地工作(in-place)的额外空间为O(1)——只使用常数个变量。递归算法的空间复杂度=递归深度——每次递归调用需要分配栈帧。

示例——斐波那契数的递归实现：

int fib_recursive(int n) {
    if (n <= 1) return n;
    return fib_recursive(n-1) + fib_recursive(n-2);
}

时间复杂度O(2ⁿ)——空间复杂度O(n)(递归栈深度为n)。迭代版可优化到O(n)时间和O(1)空间。

大O/Ω/Θ的严格区别

• 大O(上界)：f(n)=O(g(n))∃c>0,n₀≥1,n≥n₀时f(n)≤c·g(n)
• 大Ω(下界)：f(n)=Ω(g(n))∃c>0,n₀≥1,n≥n₀时f(n)≥c·g(n)
• 大Θ(确界)：同时满足O和Ω——g(n)是f(n)的渐近紧确界

通常说算法复杂度为某个值时——一般指最坏情况的上界(O)。在对比算法好坏时——更关心大O(保证算法在输入最坏时能忍受的极限)。

复习检查

1. O(1)是否意味着算法运行时间恒为1秒？用实际与n无关但可能执行上千条的代码解释O(1)的真正含义。

2. 两个嵌套循环每个从0到n-1——这就是O(n²)。如果外循环n次、内循环i(i从0递增到n-1)次——总执行次数是多少——复杂度是O(n²)吗？

3. 空间复杂度和时间复杂度的交换——使用缓存(用空间换时间)——一个原本O(2ⁿ)的递归斐波那契加上记忆化(o(n)空间)后时间复杂度变成了多少？

4. 二分查找的时间复杂度为什么是O(log n)——每次数组长度基本减半——证明log n的底数为什么在O中不重要。

5. 最好/最坏/平均时间复杂度的区别——快速排序为什么平均是O(n log n)而最坏是O(n²)？