时间复杂度和大O表示法(笔记)

大O表示法

1
2
3
2          O(1)     一个常数,复杂度固定不变
2n+10 O(n) 随着n的变化而变化,复杂度由n决定
5n^2 O(n^2) 随着n^2的变化而变化,复杂度由n^2决定

常用的时间复杂度

  1. O(1) 常量时间:给定一个大小为n的输入,该算法只需要一步就可以完成任务。
  2. O(log n) 对数时间:给定大小为n的输入,该算法每执行一步,它完成任务所需要的步骤数目会以一定的因子减少。
  3. O(n) 线性时间:给定大小为n的输入,该算法完成任务所需要的步骤直接和n相关(1对1的关系)。
  4. O(n²) 二次方时间:给定大小为n的输入,完成任务所需要的步骤是n的平方。
  5. O(C^n) 指数时间:给定大小为n的输入,完成任务所需要的步骤是一个常数的n次方(非常大的数字)。

每一个复杂度完成任务所需要的步骤数

1
2
3
4
5
6
let n = 16;
O(1) = 1 step;
O(log n) = 4 steps;
O(n) = 16 steps;
O(n^2) = 256 steps;
O(2^n) = 65535 steps;

代码示例

数据结构
1
2
3
4
5
6
7
8
const friends = {
'Mark': true,
'Amy': true,
'Carl': false,
'Ray': true,
'Laura': false
};
const sortedAges = [22, 24, 27, 29, 31];
O(1) 常量时间
1
2
3
4
function isFriend(name) {
return friends[name];
}
isFriend('Mark'); //Return true 一步操作即可获取到所要结果
O(log n) 对数时间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function thisOld(num, arr) {
const len = arr.length,
mid = Math.floor(len/2);

if (arr[mid] === num) return true;

// 只需要在大于mid的值中搜索即可
if (num > mid) {
for (let i = mid + 1, i < len; i++) {
if (arr[i] === num) return true;
}
return false;
}

// 只需要在小于mid的值中搜索即可
if (num < mid) {
for (let i = mid - 1, i > 0; i--) {
if (arr[i] === num) return true;
}
return false;
}
}

thisOld(29, sortedAges); //return true;
O(n) 线性时间
1
2
3
4
5
6
7
8
9
10
11
function addAges(arr) {
let sum = 0;
const len = arr.length;

for (let i = 0; i < len; i++) {
sum += arr[i];
}
return sum;
}

addAges(sortedAges); //133
O(n²) 二次方时间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
function addedAges(arr) {
let addedAge = [];
const len = arr.length;

for (let i = 0; i < len; i++) {
for (let j = i + 1; j < len; j++) {
addedAge.push(arr[i] + arr[j]);
}
}

return addedAge;
}

addedAges(sortedAges); //[46, 49, 51, 53, 51, 53, 55, 56, 58, 60]
O(2^n) 指数时间
1
//尝试找出长度为n的密码中所以字符的组合

参考文档

白话算法:时间复杂度和大O表示法