大O复杂度 #

分析如下代码的复杂度:

示例1：线性复杂度 #

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

假设每行代码执行时间为 unit_time：

• 第2、3行：各1个unit_time
• 第4、5行：各执行n次，共2n个unit_time
• 总时间：T(n) = (2n+2) × unit_time

示例2：平方复杂度 #

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

• 第2、3、4行：各1个unit_time
• 第5、6行：执行n次，共2n个unit_time
• 第7、8行：执行n²次，共2n²个unit_time
• 总时间：T(n) = (2n²+2n+3) × unit_time

大O表示法 #

代码执行时间T(n)与执行次数成正比，可以表示为：

T(n) = O(f(n))

其中：

• T(n)：代码执行时间
• n：数据规模大小
• f(n)：代码执行次数总和
• O：表示成正比关系

简化原则：当n很大时，低阶、常量、系数都可以忽略，只保留最大量级。

因此：

• 示例1：T(n) = O(n)
• 示例2：T(n) = O(n²)

大O时间复杂度表示代码执行时间随数据规模增长的变化趋势，也叫渐进时间复杂度。