时间复杂度

算法的时间复杂度是指程序中语句执行次数的总和。

对在程序中所有语句执行次数相加的结果：

• 去掉结果中的常数项
• 只保留最高阶项

则得到最后的时间复杂度T(n) = O(f(n))表示。

常见的时间复杂度

O(1)，O(log₂n) ，O(n)，O(nlog₂n)，O(n²)，O(n³)，O(2^n)

它们的复杂度依次递增

O(1) < O(log₂n) < O(n) < O(nlog₂n) < O(n²) < O(n³) << O(2^n)

循环执行次数的判断

for(let i = 0; i < n; i++)：执行n次

for(let i = 0; i < n - i; i++)：执行n-i次

eg1

function print() {
  for (let i = 0; i < n; i++) {
    // n次
    console.log(i); //  n次
  }
}

print();

则最后的时间复杂度为O(n)，O(n)也被称为线性阶/线性数量级：

eg2

function sum(m, n) {
  let s = 0;
  for (let i = 0; i < m; i++) {
    // m次
    for (let j = 0; j < n; j++) {
      // m*n次
      s += 1; // m*n次
    }
    console.log(s); // m次
  }
}

sum(m, n);

则最后的时间复杂度为O(n²)，O(n²)也被称为平方阶/平方数量级:

当 m = n 时

eg3

function sum(n) {
  let s = 0; // 1次
  for (let i = 0; i < n; i++) {
    // n次
    for (let j = 0; j < i; j++) {
      // 1+2+...+n
      s += 1; // 1+2+...+n
    }
    console.log(s); // n次
  }
}

sum(n);

则最后的时间复杂度为O(n²):

eg4

冒泡排序的时间复杂度，冒泡排序的基本思路就是内层对比，每一轮内层循环结束就是把最大/最小的数换到开头或者结尾的位置去

function bubble(arr) {
  const n = arr.length; // 1次
  for (let i = 1; i < n; i++) {
    // n - 1次
    for (let j = 0; j < n - i; j++) {
      // (n - 1)+(n - 2)+...+1
      if (arr[j] > arr[j + 1]) {
        // (n - 1)+(n - 2)+...+1
        const temp = arr[j]; // 0 或 (n - 1)+(n - 2)+...+1
        arr[j] = arr[j + 1]; // 0 或 (n - 1)+(n - 2)+...+1
        arr[j + 1] = temp; // 0 或 (n - 1)+(n - 2)+...+1
      }
    }
  }
  console.log(arr);
}

对于上面从小到大排列的算法，冒泡排序的时间复杂度需要考虑最好和最坏的情况：

• 最好的情况：数组本身已经有序，从小到大排列好了，那么时间复杂度为O(n²)

• 最坏的情况：数组完全倒序，那么时间复杂度为O(n²)

所以最好和最坏都是O(n²)