时间复杂度分析

时间复杂度分析 #

分析代码时间复杂度有三个实用方法：

1. 关注循环执行次数最多的代码 #

只分析循环执行次数最多的代码段，其复杂度就是整段代码的复杂度。

int cal(int n) {
  int sum = 0;
  int i = 1;
  for (; i <= n; ++i) {
    sum = sum + i;
  }
  return sum;
}

第2、3行是常量级，第4、5行执行n次，所以时间复杂度为O(n)。

2. 加法法则 #

总复杂度等于量级最大的那段代码的复杂度。

int cal(int n) {
  int sum_1 = 0;
  int p = 1;
  for (; p < 100; ++p) {
    sum_1 = sum_1 + p;
  }

  int sum_2 = 0;
  int q = 1;
  for (; q < n; ++q) {
    sum_2 = sum_2 + q;
  }

  int sum_3 = 0;
  int i = 1;
  int j = 1;
  for (; i <= n; ++i) {
    j = 1; 
    for (; j <= n; ++j) {
      sum_3 = sum_3 + i * j;
    }
  }

  return sum_1 + sum_2 + sum_3;
}

第一段：O(1) - 常量级
第二段：O(n) - 线性级
第三段：O(n²) - 平方级

总复杂度：O(n²)

公式：如果 T1(n)=O(f(n))，T2(n)=O(g(n))，那么 T(n)=O(max(f(n), g(n)))

3. 乘法法则(函数嵌套场景) #

嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。

int cal(int n) {
  int ret = 0; 
  int i = 1;
  for (; i < n; ++i) {
    ret = ret + f(i);
  } 
} 

int f(int n) {
  int sum = 0;
  int i = 1;
  for (; i < n; ++i) {
    sum = sum + i;
  } 
  return sum;
}

cal()函数：T1(n) = O(n)
f()函数：T2(n) = O(n)
总复杂度：T(n) = T1(n) × T2(n) = O(n²)

公式：如果 T1(n)=O(f(n))，T2(n)=O(g(n))，那么 T(n)=O(f(n)×g(n))