复杂度分析

为什么需要复杂度分析

传统借助计算机监控的事后统计法有非常大的局限性，理由如下

1. 测试结果非常依赖测试环境，不同的环境可能出现完全不同的结果
2. 测试结果受数据规模的影响很大。比如在小规模的数据排序下，插入排序可能比快速排序要快 我们需要一个不用具体的测试数据来测试，可以粗略估计算法执行效率的方法，这个方法就是复杂度分析

大 O 复杂度表示法

所有代码的执行时间 T(n) 与每行代码的执行次数 f(n) 成正比，即：

• T(n): 代码执行的时间
• n: 数据规模的大小
• f(n): 每行代码执行次数总和
• O: 表示代码的执行时间 T(n) 与 f(n) 表达式成正比

表示的是代码执行时间随数据规模增长的变化趋势，即时间复杂度

时间复杂度分析技巧

1. 只关注循环执行次数最多的代码
2. 加法法则：总复杂度等于量级最大的那段代码的复杂度
3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

时间复杂度分析案例

1. O(1)：多数情况下，无循环、无递归，基本都是 O(1)

 const i = 8;
 const j = 6;
 const sum = i + j;

2. O(logn)、O(nlogn)

 let i = 1;
 while (i <= n)  {
   i = i * 2;
 }

3. O(m+n)、O(m*n)

function cal(m, n) {
  let sum_1 = 0;
  for (let i = 1; i < m; ++i) {
    sum_1 += i;
  }
 
  let sum_2 = 0;
  for (let j = 1; j < n; ++j) {
    sum_2 += j;
  }
 
  return sum_1 + sum_2;
}

4. 最好情况时间复杂度：第一个元素就是要查找的变量x，那么复杂度就是 O(1) 最坏情况时间复杂度：数组中不存在变量x，那么复杂度就是O(n)

function find(array, n, x) {
  let pos = -1;
  for (let i = 0; i < n; ++i) {
    if (array[i] === x) {
      pos = i;
      break; // 找到元素后跳出循环
    }
  }
  return pos;
}
 
// 调用函数示例
const array = [1, 3, 5, 7, 9]; // 假设这是我们的数组
const n = array.length; // 数组的长度
const x = 5; // 我们要找的元素
console.log(find(array, n, x)); // 输出找到的索引位置

空间复杂度

表示算法的存储空间与数据规模之间的增长关系。

function print(n) {
  let i = 0;
  let a = Array(n);
  for (i; i < n; ++i) {
    a[i] = i * i;
  }
 
  for (i = n - 1; i >= 0; --i) {
    console.log(a[i]);
  }
}