Chapter-1 Algorithm Analysis

一、Algorithm Definition

Algorithm是指令的有限集合，遵循这些指令可以完成特定的任务。此外，所有算法都必须满足以下5条核心准则：

1. Input：有0个或多个由外部提供的量

2. Output：至少产生一个输出量

3. 确定性（Definiteness）：每条指令都清晰、无歧义

4. 有穷性(Finiteness)：对于算法的所有用例，在执行有限步之后必然终止

5. 可行性(Effectiveness)：每条指令都必须足够基础，原则上可以由人仅用纸笔完成；仅满足确定性是不够的，操作还必须是可实现的

示例：选择排序(Selection Sort)

功能：将 n ≥ 1 个整数按升序排列 在当前未排序的整数中，找到最小值，将其放到已排序序列的下一个位置。

for ( i = 0; i < n; i++) {
    // 检查list[i]到list[n-1]，找到最小值的下标min
    交换 list[i] 和 list[min];
}

排序核心动作 = 查找未排序区间的最小值 + 与当前区间首元素交换

二、算法分析的核心内容

分析算法核心是评估时间开销(Time Complexity)和空间开销(Space Complexity)，而非和机器、编译器绑定的具体运行时间。

分析的前提假设

为了剥离机器差异，我们做3个基础假设：

1. 指令按顺序执行(executed sequentially)

2. 每条指令都是简单操作，执行恰好花费1个时间单位

3. 整数大小固定，内存无限(infinite memory)

我们通常聚焦两个核心时间复杂度函数：

• \(T_{avg}(N)\)：平均情况时间复杂度(Average Case Time Complexity)，输入规模为N时的平均运行时

• \(T_{worst}(N)\)：最坏情况时间复杂度(Worst Case Time Complexity)，输入规模为N时的最大运行时间

若算法有多个输入维度，复杂度函数可包含多个参数。

---

示例1：矩阵加法(Matrix Addition)

// 矩阵a + 矩阵b = 矩阵c，矩阵维度为rows行cols列
void add ( int a[][ MAX_SIZE ], 
           int b[][ MAX_SIZE ], 
           int c[][ MAX_SIZE ],
           int rows, int cols )
{
    int i, j;
    for ( i = 0; i < rows; i++ )
          for ( j = 0; j < cols; j++ )
                c[ i ][ j ] = a[ i ][ j ] + b[ i ][ j ];
}

精确步数计算：\(T(rows, cols ) = 2 \times rows \times cols + 2 \times rows + 1\)

问题：如果 rows 远大于 cols 该如何处理？

回答：交换 rows 和 cols 的遍历顺序，优化内存缓存命中率。

---

示例2：数组求和的迭代实现(Iterative Summation)

float sum ( float list[], int n )
{  /* 累加数组中的所有数字 */
   float tempsum = 0; 
   int i; 
   for ( i = 0; i < n; i++ ) 
       tempsum += list[i];
   return tempsum;
}

精确步数计算：\(T_{sum}(n) = 2n + 3\)

---

示例3：数组求和的递归实现(Recursive Summation)

float rsum ( float list[], int n )
{  /* 递归累加数组中的所有数字 */
   if ( n )    
       return rsum(list, n-1) + list[n - 1];
   return 0;
}

精确步数计算：\(T_{rsum}(n) = 2n + 2\)

虽然递归实现的步数公式数值更小，但每一步的实际执行耗时远高于迭代。

我们真的有必要精确计算每一步的执行次数吗？

结论：精确计数非常繁琐，且在不同机器、编译器下无普适性。我们真正需要关注的，是运行时间随输入规模增长的趋势(Growth Trend of Runtime with Input Size)。

---

三、渐近记号(Asymptotic Notation)

预测运行时间随输入规模N的增长趋势，从而对比两个程序的时间复杂度。真正需要关注的是时间函数\(T_p\)的渐近行为(Asymptotic Behavior)。

举个例子：假设 \(T_{p1}(N) = c_1N^2 + c_2N\)，\(T_{p2}(N) = c_3N\)。哪个更快？

无论\(c_1、c_2、c_3\)的取值如何，总会存在一个阈值\(n_0\)，当所有 \(N > n_0\) 时，都有 \(T_{p1}(N) > T_{p2}(N)\)。

结论：只要知道\(T_{p1}\)的增长量级约为\(N^2\)，\(T_{p2}\)约为\(N\)，那么当输入规模N足够大时，\(P_2\)一定更快。

---

2.1 渐近记号的定义

1. 大O记号（上界）(Big O Notation, Upper Bound) 【定义】若存在正常数\(c\)和\(n_0\)，使得对于所有 \(N ≥ n_0\)，都有 \(T(N) ≤ c·f(N)\)，则记 \(T(N) = O(f(N))\)。

   \(T(N)\)的增长速度不会超过\(f(N)\)，\(f(N)\)是\(T(N)\)的时间上界，对应算法的最坏情况上限。

2. 大Ω记号（下界）(Big Omega Notation, Lower Bound) 【定义】若存在正常数\(c\)和\(n_0\)，使得对于所有 \(N ≥ n_0\)，都有 \(T(N) ≥ c·g(N)\)，则记 \(T(N) = Ω(g(N))\)。

   \(T(N)\)的增长速度不会低于\(g(N)\)，\(g(N)\)是\(T(N)\)的时间下界，用于描述算法的理论性能下限。

3. Θ记号（紧界）(Big Theta Notation, Tight Bound) 【定义】当且仅当 \(T(N) = O(h(N))\) 且 \(T(N) = Ω(h(N))\) 时，记 \(T(N) = Θ(h(N))\)。

   \(T(N)\)的增长速度与\(h(N)\)完全相当，\(h(N)\)是\(T(N)\)的紧确界，说明算法的上下界一致。

4. 小o记号（非紧上界）(Little o Notation, Non-tight Upper Bound) 【定义】若 \(T(N) = O(p(N))\) 且 \(T(N) ≠ Θ(p(N))\)，则记 \(T(N) = o(p(N))\)。

   \(T(N)\)的增长速度严格慢于\(p(N)\)，是不紧的上界。

---

2.2 使用规范

• 对于大O记号，\(2N + 3 = O(N) = O(N^{k≥1}) = O(2^N) = ...\)，我们始终取最小的\(f(N)\)，也就是最紧的上界。

• 对于大Ω记号，\(2N + N^2 = Ω(2^N) = Ω(N^2) = Ω(N) = Ω(1) = ...\)，我们始终取最大的\(g(N)\)，也就是最紧的下界。

---

2.3 渐近记号运算规则

1. 若 \(T_1(N) = O(f(N))\) 且 \(T_2(N) = O(g(N))\)，则：

   • (a) \(T_1(N) + T_2(N) = max( O(f(N)), O(g(N)) )\)（加法取最高阶，低阶项可忽略）

   • (b) \(T_1(N) * T_2(N) = O( f(N) * g(N) )\)（乘法阶数相加）

   • 若 \(T(N)\) 是一个k次多项式，则 \(T(N) = Θ(N^k)\)。
   • 对于任意常数k，都有 \(log^k N = O(N)\)。这说明对数函数的增长速度极其缓慢，几乎接近常数级。

重要注意事项：渐近对比的前提是输入规模N足够大。

例如：\(T_{p1}(N) = 10^6 N\)，\(T_{p2}(N) = N^2\)。虽然\(Θ(N^2)\)的增长速度比\(Θ(N)\)快，但当 \(N < 10^6\) 时，\(P_2\)仍然比\(P_1\)更快。

---

2.4 常见复杂度的增长速度排序

从慢到快（性能从优到差）依次为： \(log\ n\) < \(n\) < \(n\ log\ n\) < \(n^2\) < \(2^n\)

---

2.5 时间复杂度分析规则

1. for循环(for Loops)：for循环的运行时间，最多为循环内语句（包括循环判断）的运行时间 × 循环迭代次数。
2. 嵌套for循环(Nested for Loops)：嵌套循环内语句的总运行时间，为语句的运行时间 × 所有循环的规模乘积。
3. 连续语句(Consecutive Statements)：运行时间相加（最终取最大值，即最高阶项）。
4. IF/ELSE语句(IF/ELSE Statements)：对于代码片段

   if ( Condition )  S1;
   else  S2;
   

   运行时间不超过「条件判断的运行时间 + S1和S2中运行时间的较大值」。
5. 递归(Recursions)：递归的时间复杂度需通过递推式分析。

---

示例1：矩阵加法的渐近复杂度分析

void add ( int a[][ MAX_SIZE ], 
           int b[][ MAX_SIZE ], 
           int c[][ MAX_SIZE ],
           int rows, int cols )
{
    int i, j;
    for ( i = 0; i < rows; i++ )
          for ( j = 0; j < cols; j++ )
                c[ i ][ j ] = a[ i ][ j ] + b[ i ][ j ];
}

- 外层循环：\(Θ(rows)\)

• 内层循环+赋值语句：\(Θ(rows × cols)\)

• 整体渐近复杂度：\(T(rows, cols) = Θ(rows × cols)\)

---

示例2：斐波那契数列(Fibonacci Number)的递归实现

递推定义：\(Fib(0) = Fib(1) = 1\)，\(Fib(n) = Fib(n-1) + Fib(n-2)\)

long int Fib ( int N )
{
    if ( N <= 1 )
        return 1;
    else
        return Fib( N - 1 ) + Fib( N - 2 );
}

递推式：\(T(N) = T(N-1) + T(N-2) + 2\) 可通过数学归纳法证明：\(T(N) ≥ Fib(N)\)，\(T(N)\)呈指数级增长(Exponential Growth)。

为什么这个递归实现的效率极差？

存在大量的重复计算，比如\(Fib(5)\)会计算\(Fib(4)\)和\(Fib(3)\)，\(Fib(4)\)又会重复计算\(Fib(3)\)，随着N增大，重复计算量爆炸式增长。时间复杂度是指数级\(O(φ^n)\)（φ为黄金分割比≈1.618）

---

四、算法对比：最大子序列和问题

Maximum Subsequence Sum Problem

给定N个整数（可负）\(A_1, A_2, …, A_N\)，求子序列和 \(\sum_{k=i}^j A_k\) 的最大值；若所有整数均为负数，规定最大和为0。

---

算法1：三重循环

int  MaxSubsequenceSum ( const int A[ ],  int  N ) 
{ 
    int  ThisSum,  MaxSum,  i,  j,  k; 
    /* 1*/  MaxSum = 0;   /* 初始化最大和 */
    /* 2*/  for( i = 0; i < N; i++ )  /* 子序列起点i */
    /* 3*/      for( j = i; j < N; j++ ) {   /* 子序列终点j */
    /* 4*/          ThisSum = 0; 
    /* 5*/          for( k = i; k <= j; k++ ) 
    /* 6*/              ThisSum += A[ k ];  /* 累加A[i]到A[j]的和 */
    /* 7*/          if ( ThisSum > MaxSum ) 
    /* 8*/              MaxSum = ThisSum;  /* 更新最大和 */
            }  /* end for-j and for-i */
    /* 9*/  return  MaxSum; 
} 

• \(T(N) = O(N^3)\)

• 枚举所有可能的子序列起点i和终点j，通过内层循环k计算每个子序列的和，最终保留最大值。

• 存在大量重复计算。计算i=0,j=3的和后，计算i=0,j=4时，会重复累加A[0]~A[3]。

---

算法2：双层循环

int  MaxSubsequenceSum ( const int A[ ],  int  N ) 
{ 
    int  ThisSum,  MaxSum,  i,  j; 
    /* 1*/  MaxSum = 0;   /* 初始化最大和 */
    /* 2*/  for( i = 0; i < N; i++ )  {   /* 子序列起点i */
    /* 3*/      ThisSum = 0; 
    /* 4*/      for( j = i; j < N; j++ ) {   /* 子序列终点j */
    /* 5*/          ThisSum += A[ j ];  /* 直接累加A[j]，复用前一次的和 */
    /* 6*/          if ( ThisSum > MaxSum ) 
    /* 7*/              MaxSum = ThisSum;  /* 更新最大和 */
        }  /* end for-j */
    }  /* end for-i */
    /* 8*/  return  MaxSum; 
} 

\(T(N) = O(N^2)\)

---

分治法（Divide and Conquer）

分治法的核心是“分而治之”，将大问题拆解为规模更小的子问题，递归求解后再合并结果。对于最大子序列和问题，最大和仅存在三种可能： 1. 完全位于数组的左半部分 2. 完全位于数组的右半部分 3. 跨越数组中点，同时包含左半部分的后缀和右半部分的前缀

最终结果为三种情况的最大值。

示例推演

以数组 [4, -3, 5, -2, -1, 2, 6, -2] 为例： 1. 分：将数组拆分为左半部分[4,-3,5,-2]、右半部分[-1,2,6,-2] 2. 治：递归求解左半部分最大和为6，右半部分最大和为8 3. 计算跨越中点的最大和，左半部分最大后缀和为4-3+5=6，右半部分最大前缀和为-1+2+6=7，合计11 4. max(6,8,11) = 11

复杂度

递推式：\(T(N) = 2T(N/2) + cN\)，其中\(T(1) = O(1)\) - \(2T(N/2)\)：递归求解左右两个规模为N/2的子问题

• \(cN\)：线性时间内计算跨越中点的最大和

递推展开推导：

$$ \begin{align} T(N) &= 2T(N/2) + cN \ &= 2[2T(N/2^2) + cN/2] + cN = 2^2T(N/2^2) + 2cN \ &\dots \ &= 2^k O(1) + c k N \quad (N/2^k = 1 \implies k=log_2N) \ &= N \cdot O(1) + cN logN \ &= O(N logN) \end{align} $$

\(T(N) = O(N logN)\)，该结论对N不是2的整数次幂的情况同样成立。

---

在线算法

int MaxSubsequenceSum( const int  A[ ],  int  N ) 
{ 
    int  ThisSum, MaxSum, j; 
    /* 1*/  ThisSum = MaxSum = 0; 
    /* 2*/  for ( j = 0; j < N; j++ ) { 
    /* 3*/      ThisSum += A[ j ]; 
    /* 4*/      if  ( ThisSum > MaxSum ) 
    /* 5*/       MaxSum = ThisSum; 
    /* 6*/      else if ( ThisSum < 0 ) 
    /* 7*/       ThisSum = 0;
    }  /* end for-j */
    /* 8*/  return MaxSum; 
} 

• 在线算法：在任意时刻，算法都能对已读入的数据给出正确的答案，无需预知全部输入数据，也不需要回退读取历史数据。

• 核心优化逻辑：

• 遍历数组时维护ThisSum和MaxSum
• 若ThisSum变为负数，直接重置为0。因为负数的前缀不可能让后续的子序列和更大，直接舍弃之前的子序列，从下一个元素重新开始累加
• 每次累加后，若ThisSum大于MaxSum，更新全局最大值

示例推演（数组[-1,3,-2,4,-6,1,6,-1]）：

遍历元素	ThisSum变化	MaxSum变化	核心操作
-1	0→-1→0	0	和为负，重置为0
3	0→3	3	更新最大值
-2	3→1	3	仍为正，保留
4	1→5	5	更新最大值
-6	5→-1→0	5	和为负，重置为0
1	0→1	5	保留
6	1→7	7	更新最大值
-1	7→6	7	保留

最终结果为7，与实际最大子序列[1,6]的和一致。

\(T(N) = O(N)\)，数组仅需一次遍历，是该问题的理论最优解法。

---

四种算法的运行时间实测对比

输入规模N	算法1 O(N³)	算法2 O(N²)	算法3 O(N logN)	算法4 O(N)
10	0.00103	0.00066	0.00045	0.00034
100	0.47015	0.00486	0.01112	0.00063
1000	448.77	0.05843	1.1233	0.00333
10000	NA	0.68631	111.13	0.03042
100000	NA	8.0113	NA	0.29832

---

五、运行时间中的对数

若一个算法能在每一步操作中，将待处理的问题规模按固定比例削减（通常是减半），那么该算法的时间复杂度通常为\(O(logN)\)。对数函数的增长速度极慢，在大规模数据下，对数时间算法的性能远超线性、多项式时间算法。

二分查找（Binary Search）

问题定义

给定已升序排列的数组 \(A[0] ≤ A[1] ≤ … ≤ A[N-1]\) 和目标值X，查找X在数组中的下标；若X不存在，返回-1。

代码实现

int BinarySearch ( const ElementType  A[ ], 
                   ElementType  X,  int  N ) 
{ 
    int  Low, Mid, High; 
    /* 1*/  Low = 0;  High = N - 1;  /* 初始化查找区间 */
    /* 2*/  while ( Low <= High ) { 
    /* 3*/      Mid = ( Low + High ) / 2;  /* 取区间中点 */
    /* 4*/      if ( A[ Mid ] < X ) 
    /* 5*/          Low = Mid + 1;  /* X在右半区间，更新左边界 */
            else 
    /* 6*/          if ( A[ Mid ] > X ) 
    /* 7*/              High = Mid - 1;  /* X在左半区间，更新右边界 */
                else 
    /* 8*/              return  Mid; /* 找到目标，返回下标 */
    }  /* end while */
    /* 9*/  return  NotFound; /* NotFound定义为-1，未找到目标 */
} 

• 最坏时间复杂度：\(T_{worst}(N) = O(log N)\)

• 核心逻辑：每次通过中点Mid将查找区间缩小一半，最坏情况下，直到查找区间为空才结束，最多需要\(log_2N\)次比较，因此时间复杂度为对数级。

• 适用场景：静态数据、已完成排序的场景，例如字典查词、静态数据库查询等；若数据频繁增删，排序的开销会抵消二分查找的优势。

---

欧几里得算法（Euclid’s Algorithm）

求两个非负整数 \(a\) 和 \(b\) 的最大公约数（Greatest Common Divisor, GCD），即能同时整除 \(a\) 和 \(b\) 的最大正整数。

辗转相除法：基于数学性质 \(\text{gcd}(a, b) = \text{gcd}(b, a \mod b)\)，不断将问题规模缩小，直到 \(b=0\)，此时 \(a\) 即为最大公约数。若 \(a < b\)，第一次取模后会自动交换两者位置，无需额外处理。

#include <stdio.h>
#include <stdlib.h>  // 用于abs()函数

/* 欧几里得算法：求a和b的最大公约数 */
int gcd(int a, int b) {
    a = abs(a);  // 处理负数，取绝对值
    b = abs(b);

    int temp;
    while (b != 0) {
        temp = a % b;  // 计算a mod b
        a = b;         // 将b赋值给a
        b = temp;      // 将余数赋值给b，进入下一轮迭代
    }
    return a;  // 当b=0时，a即为最大公约数
}

int main() {
    int num1 = 12345, num2 = 67890;
    printf("gcd(%d, %d) = %d\n", num1, num2, gcd(num1, num2));
    return 0;
}

\(O(\log \min(a,b))\)。每次迭代后，问题规模至少减半，因此迭代次数为对数级。

以 \(\text{gcd}(67890, 12345)\) 为例： 1. \(67890 \mod 12345 = 6165\)，问题变为 \(\text{gcd}(12345, 6165)\) 2. \(12345 \mod 6165 = 15\)，问题变为 \(\text{gcd}(6165, 15)\) 3. \(6165 \mod 15 = 0\)，此时 \(b=0\)，返回 \(a=15\) 最终结果为15，与实际最大公约数一致。

---

快速幂算法（Exponentiation）

高效计算 \(x^n\)（\(x\) 为实数，\(n\) 为非负整数），避免直接循环相乘的 \(O(n)\) 时间复杂度。

分治思想：将幂运算按指数 \(n\) 的奇偶性拆分，减少乘法次数： - 若 \(n\) 为偶数：\(x^n = (x^{n/2})^2\) - 若 \(n\) 为奇数：\(x^n = (x^{(n-1)/2})^2 \cdot x\) 通过递归或迭代不断拆分，直到 \(n=0\)（返回1）或 \(n=1\)（返回x）。

#include <stdio.h>

/* 快速幂算法：计算x的n次幂，n为非负整数 */
double fast_pow(double x, int n) {
    double result = 1.0;
    double base = x;

    while (n > 0) {
        if (n % 2 == 1) {  // 若n为奇数，将当前base乘到结果中
            result *= base;
        }
        base *= base;  // base平方，对应分治中的(x^(n/2))^2
        n = n / 2;     // 指数减半（整数除法自动向下取整）
    }
    return result;
}

int main() {
    double x = 2.0;
    int n = 10;
    printf("%.0f^%d = %.0f\n", x, n, fast_pow(x, n));
    return 0;
}

时间复杂度：\(O(\log n)\)。每次迭代指数减半，最多需要 \(\log_2n\) 次乘法操作。

以 \(2^{10}\) 为例： 1. 初始：result=1, base=2, n=10（偶数） - base 变为 \(2^2=4\)，n 变为 \(5\) 2. n=5（奇数）： - result 变为 \(1 \times 4=4\)，base 变为 \(4^2=16\)，n 变为 \(2\) 3. n=2（偶数）： - base 变为 \(16^2=256\)，n 变为 \(1\) 4. n=1（奇数）： - result 变为 \(4 \times 256=1024\)，base 变为 \(256^2\)，n 变为 \(0\) 5. 循环结束，返回 result=1024，与 \(2^{10}=1024\) 一致。

---

六、算法分析结果的检验

完成算法的理论复杂度分析后，通过以下两种方法验证分析结果是否正确。

翻倍测试

根据复杂度的增长特性，观察输入规模翻倍后，运行时间的增长比例是否符合理论预期。 - 若\(T(N) = O(N)\)，则\(T(2N)/T(N) ≈ 2\)

• 若\(T(N) = O(N^2)\)，则\(T(2N)/T(N) ≈ 4\)

• 若\(T(N) = O(N^3)\)，则\(T(2N)/T(N) ≈ 8\)

• 若\(T(N) = O(logN)\)，则\(T(2N)/T(N) ≈ 1\)

• 若\(T(N) = O(N logN)\)，则\(T(2N)/T(N) ≈ 2\)

极限验证

通过极限计算，验证理论上界\(f(N)\)的紧确性。 若\(T(N) = O(f(N))\)，则需满足： $\(\lim_{N \to \infty} \frac{T(N)}{f(N)} = C\)$ 其中C为正的常数。

• 若极限为0：说明\(T(N) = o(f(N))\)，\(f(N)\)是一个非紧的上界，可找到更紧的上界

• 若极限为无穷大：说明\(f(N)\)不是\(T(N)\)的上界，理论分析错误