2019-09-02

JS►algorithm

algorithm

关于算法的基础知识

此外，算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。

时间频度

　一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)

时间复杂度

算法时间复杂度的本质是算法的执行时间，也就是算法中所有语句频度（执行次数）之和。
假设问题规模为n，则语句频度可以表示成一个关于问题规模的函数 T(n)，那么算法时间复杂度也就可以用T(n)。
当问题规模n很大时，精确计算T(n)是很难实现的。因此可以通过它的变化趋势和规律反映算法的耗时。

渐进时间复杂度

若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n))
称Ｏ(f(n)) 为算法的渐进时间复杂度
算法时间复杂度和渐进算法时间复杂度在实际的算法分析过程中是不予区分的，渐进时间复杂度可以简称为时间复杂度。
T(n) = O(f(n)) 表示存在一个常数C，使得在当n趋于正无穷时总有 T(n) ≤ C f(n), 当n趋于正无穷时T(n)的上界是C f(n), 虽对f(n)没有规定，但是一般尽可能取简单的函数（即最坏情况）。

例

O(2n²+n +1) = O (3n²+n+3) = O (7n² + n) = O (n²) ，一般都只用O(n²)

常见的时间复杂度

常数阶O(1)
对数阶O(log₂n)
线性阶O(n)
线性对数阶O(nlog₂n)
平方阶O(n²)
立方阶O(n³)
k次方阶O(n^k)
指数阶O(2ⁿ)

常见的算法时间复杂度由小到大依次为

Ο(1)＜Ο(log₂ⁿ)＜Ο(n)＜Ο(nlog₂ⁿ)＜Ο(n²)＜Ο(n³)＜Ο(2ⁿ)

求解算法的时间复杂度

简单理解的话，时间复杂的优劣，其实就是数学中各类基础函数的应用，如下图(来源wiki)。

1、对于一些简单的输入输出语句或赋值语句，不存在遍历循环，近似认为需要O(1)

2、找出算法中的基本语句；算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体；

3、计算基本语句的执行次数的数量级；只要保证基本语句执行次数的函数中的最高次幂正确即可

4、如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。

第一个for循环的时间复杂度为Ο(n)，第二个for循环的时间复杂度为Ο(n²)，则整个算法的时间复杂度为Ο(n+n²)=Ο(n²)

let sub = 0
let sub2 = 0
let n = 5

for (var j = 0; j < n; j++) {
  sub++
    for (var i = 0; i < n; i++) {
       sub2++
    }
}

console.log(sub)    // 5
console.log(sub2)   // 25

5、对于顺序结构采用求和法则:

若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1(n)+T2(n)=O(max(f(n), g(n)))
特别地,若T1(m)=O(f(m)), T2(n)=O(g(n)),则 T1(m)+T2(n)=O(f(m) + g(n))

6、对于选择结构,如if语句,需注意的是检验条件也需要O(1)时间

7、对于循环结构,一般可用乘法法则：

若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1T2=O(f(n)g(n))

8、对于复杂的算法,可以将它分成几个容易估算的部分,然后利用求和法则和乘法法则技术整个算法的时间复杂度

9、其他情况（始终考虑最坏情况）,若g(n)=O(f(n)), 则O(f(n))+ O(g(n))= O(f(n))； O(Cf(n)) = O(f(n))

时间复杂度分析的基本策略是：从内向外分析，从最深层开始分析。如果遇到函数调用，要深入函数进行分析

基本的简化

去掉运行时间中的所有加法常数。（例如 n2+n+1，直接变为 n2+n）

只保留最高项。（n2+n 变成 n2）

如果最高项存在但是系数不是1，去掉系数。（n2 系数为 1）

常见时间复杂度示例

O(1)

let a = 3
let b = 4
let temp = ''
temp = a  
a = b
b = temp

以上单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)

如果算法的执行时间不随着问题规模n的增加而增长，无论算法中有多少语句，其执行时间也不过是一个较大的常数。此类算法时间复杂度O(1)

O(logⁿ)

let i = 1
while(i<n)
{
    i = i * 2
}

i 1
i 1 * 2
i 1 * 2 * 2
i 1 * 2 * 2 * 2
...
...
i 1 * 2 * 2 ...x  = n   之后退出

每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。我们试着求解一下，假设循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2^n

O(n)

let a = 0                 1次
let b = 1                 1次
for (i=1;i<=n;i++) {      n + 1 次
  a = a++　　              n次
  b = (b++) * 2　　　      n次
}

最常见的for循环时间复杂度是O(n)，其实也就是数学中线性关系，T(n) = 1 + 1 + (n + 1) + 2n = 3 + 3n = O(n)

O(nlogN)

for(let m=1; m<n; m++) {
    i = 1
    while(i<n)
    {
        i = i * 2
    }
}

线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为O(logⁿ)的代码循环n遍的话，那么它的时间复杂度就是 n * O(logⁿ)，也就是了O(nlogⁿ)。

O(n²)

var a  = 0               1次
var n = 5                1次
for (i=1;i<=n;i++) {     n + 1次
  for(j=1;j<=n;j++) {    n^2次
    a++                  n^2次
  }
}

n²最简单的来自于两个for循环嵌套即可。因为Θ(2n²+n+1)=n²（1. 去低阶项 2. 去掉常数项 3.去掉高阶项的常参, 通过它的变化趋势和规律，取最坏情况，当n趋近无穷时，1，2，3的影响非常小），所以T(n)=O(n²)

空间复杂度

算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作:S(n)= O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。