C++时间复杂度详解

一、时间复杂度核心概念

1.1 为什么要研究时间复杂度

当处理大规模数据时（如计算斐波那契数列第57项），不同算法效率差异巨大：

• 递推解法：0.23秒完成

• 递归解法：需要2369秒（约40分钟）

时间复杂度是衡量算法执行效率的核心指标，用大O符号表示算法执行时间的增长趋势，与具体硬件无关。

1.2 基本定义

时间复杂度（Time Complexity）表示算法中基本操作执行次数与数据规模n的数学关系，反映算法执行时间的增长速率。记为：T(n) = O(f(n))

二、常见时间复杂度类型与示例

2.1 典型代码分析

线性时间 O(n)

for(int i=0; i<n; i++){  // 执行n次
    sum += i;            // 基本操作
}

平方时间 O(n²)

for(int i=0; i<n; i++){       // 外层n次
    for(int j=0; j<n; j++){   // 内层n次
        if(a[i][j] > max)     // 基本操作
            max = a[i][j];
    }
}

对数时间 O(logn)

int binarySearch(int arr[], int n, int x){
    int left=0, right=n-1;
    while(left <= right){     // 每次规模减半
        int mid = (left+right)/2;
        if(arr[mid] == x) return mid;
        if(arr[mid] > x) right = mid-1;
        else left = mid+1;
    }
    return -1;               // 执行次数：log2n
}

三、斐波那契数列解法对比

3.1 递推解法（动态规划）

long long fib[57] = {1,1};
for(int i=2; i<57; i++){
    fib[i] = fib[i-1] + fib[i-2];  // 基本操作执行56次
}
cout << fib[56];  // 时间复杂度O(n)

3.2 递归解法

long long fib(int n){
    if(n==1 || n==2) return 1;
    return fib(n-1) + fib(n-2);  // 时间复杂度O(2ⁿ)
}

递归树分析（n=5时）：

            fib(5)
          /         \
      fib(4)       fib(3)
     /      \       /    \
  fib(3) fib(2) fib(2) fib(1)
  /    \
fib(2) fib(1)

• 总调用次数：9次 = 2⁵ - 1 ≈ O(2ⁿ)

四、时间复杂度计算实战

4.1 双重循环特殊场景

for(int i=1; i<=n; i++){        // 外层n次
    for(int j=1; j<=n; j+=i){   // 内层n/i次
        sum += a[i][j];         // 总次数：n*(1+1/2+...+1/n)
    }
}

• 调和级数求和：Σ(1/i) ≈ ln(n) + γ（欧拉常数≈0.577）

• 时间复杂度：O(nlogn)

4.2 常见计算技巧

1. 循环次数法：

   for(int i=0; i<n; i*=2){...}  // 执行log2n次

2. 摊还分析法：

   vector<int> vec;
   for(int i=0; i<n; i++){
       vec.push_back(i);  // 均摊时间复杂度O(1)
   }

3. 主定理公式（分治算法）：

   T(n) = aT(n/b) + O(n^d)

五、算法选择原则

5.1 效率分级参考

5.2 斐波那契案例优化

• 矩阵快速幂：时间复杂度O(logn)

  // 基于矩阵[[1,1],[1,0]]的n次幂
  long long matrix_pow(int n){
      // 实现快速幂算法
  }