跳到主要内容

算法分析

时间复杂度​

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

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

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

则得到最后的时间复杂度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)

800px-Comparison_computational_complexity.svg-164111821461425

循环执行次数的判断​

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)也被称为线性阶/线性数量级：

f(n)=n+n=2nT(n)=O(f(n))=O(2n)=O(n)f(n) = n+n = 2n \\ T(n) = O(f(n)) = O(2n) = 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²)也被称为平方阶/平方数量级:

f(n)=m+2∗m∗n+m当m=n时，O(n)=n+2n2+m=O(n2)f(n) = m + 2*m*n + m \\ 当 m = n 时， O(n) = n + 2n^2 + m = O(n^2)

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²):

f(n)=1+n+2∗(1+2+...+n)+n=1+n+2∗(n∗1+n2)+n=n2+3n+1O(n)=n2+3n+1=O(n2)f(n) = 1 + n + 2*(1+2+...+n) + n = 1 + n + 2*(n*\frac{1+n}{2}) + n = n^2 + 3n + 1 \\ O(n) = n^2 + 3n + 1 = O(n^2)

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²)
f(n)=1+(n−1)+((n−1)+(n−2)+...+1)∗2=n+2∗(n∗n−12)=n2O(n)=O(n2)f(n) = 1 + (n-1) + ((n - 1)+(n - 2)+...+1)*2 = n + 2*(n*\frac{n-1}{2}) = n^2 \\ O(n) = O(n^2)
  • 最坏的情况：数组完全倒序，那么时间复杂度为O(n²)
f(n)=1+(n−1)+((n−1)+(n−2)+...+1)∗2=n+5∗(n∗n−12)=n2O(n)=O(n2)f(n) = 1 + (n-1) + ((n - 1)+(n - 2)+...+1)*2 = n + 5*(n*\frac{n-1}{2}) = n^2 \\ O(n) = O(n^2)

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

改进时间复杂度​

冒泡排序可以通过改进算法来改进时间复杂度，这也正是分析时间复杂度的意义。

如上考虑到冒泡排序最好的情况是完全有序的情况，此时不会发生内循环的数据交换，所以给定一个变量change=false，在一轮完整的内层循环中如果发生数据交换则设置change=true，然后在外层循环判断change，如果为false则直接退出循环。

function bubble(arr) {
  const n = arr.length;
  for (let i = 1; i < n; i++) {
    let change = false;
    for (let j = 0; j < n - i; j++) {
      if (arr[j] > arr[j + 1]) {
        change = true;
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }

    if (!change) {
      console.log(arr);
      return;
    }
  }
  console.log(arr);
}