# 算法复杂度
# 大 O 表示法
用于描述算法的性能和复杂程度
| 符号 | 名称 |
|---|---|
| O(1) | 常数的 |
| O(log(n)) | 对数的 |
| O((log(n))c) | 对数多项式的 |
| O(n) | 线性的 |
| O(n2) | 二次的 |
| O(nc) | 多项式的 |
| O(cn) | 指数的 |
// O(1)
function increment (num) {
return ++num
}
// O(n)
function search (array, item) {
for (let i = 0; i < array.length; i++) {
if (item === array[i])
return i
}
return -1
}
// O(n^2) 冒泡排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# NP 完全理论概述
一般来说，如果一个算法的复杂度为 O(n^k)，其中 k 为常数，我们就认为这个算法是高效的，这就是多项式算法。
对于给定的问题，如果存在多项式算法，则计为 P(polynomial，多项式)
还有一类 NP(nondeterministic polynomial，非确定多项式)算法。如果一个问题可以在多项式时间内验证解是否正确，则计为 NP。
如果一个问题存在多项式算法，自然可以在多项式时间内验证其解。因此所有的 P 都是 NP。然而 P=NP 是否成立，仍然不得而知。