Skip to main content

算法分析

时间复杂度

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

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

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

则得到最后的时间复杂度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() < O() << 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+2mn+mm=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(n1+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+(n1)+((n1)+(n2)+...+1)2=n+2(nn12)=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+(n1)+((n1)+(n2)+...+1)2=n+5(nn12)=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);
}