[TOC] ### **算法是什么** 算法（Algorithm）是指用来操作数据、解决程序问题的一组方法。对于同一个问题，使用不同的算法，也许最终得到的结果是一样的，但在过程中消耗的资源和时间却会有很大的区别。 ### **如何衡量不同算法之间的优劣？** * 时间维度：是指执行当前算法所消耗的时间，我们通常用「时间复杂度」来描述。 * 空间维度：是指执行当前算法需要占用多少内存空间，我们通常用「空间复杂度」来描述。 #### **时间复杂度** 通用的方法就出来了：「**大O符号表示法**」，即 T(n) = O(f(n)) 例子： ``` for(i=1; i<=n; ++i) { j = i; j++; } ``` **算法的渐进时间复杂度**: 在 大O符号表示法中，时间复杂度的公式是： T(n) = O( f(n) )，其中f(n) 表示每行代码执行次数之和，而 O 表示正比例关系。 >假设每行代码的执行时间都是一样的，我们用 1颗粒时间 来表示，那么这个例子的第一行耗时是1个颗粒时间，第三行的执行时间是 n个颗粒时间，第四行的执行时间也是 n个颗粒时间（第二行和第五行是符号，暂时忽略），那么总时间就是 1颗粒时间 + n颗粒时间 + n颗粒时间 ，即 (1+2n)个颗粒时间，即： T(n) = (1+2n)\*颗粒时间，从这个结果可以看出，这个算法的耗时是随着n的变化而变化，因此，我们可以简化的将这个算法的时间复杂度表示为：T(n) = O(n) 为什么可以这么去简化呢，因为大O符号表示法并不是用于来真实代表算法的执行时间的，它是用来表示代码执行时间的增长变化趋势的。 所以上面的例子中，如果n无限大的时候，T(n) = time(1+2n)中的常量1就没有意义了，倍数2也意义不大。因此直接简化为T(n) = O(n) 就可以了。 #### **时间复杂度量级** ##### 常数阶级O(1) 无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1) ``` int i = 1; int j = 2; ++i; j++; int m = i + j; ``` ##### 线性阶O(n) for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度。 ``` for(i=1; i<=n; ++i) { j = i; j++; } ``` ##### **对数阶O(logN)** 代码： ``` int i = 1; while(i<n) { i = i * 2; } ``` 在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。我们试着求解一下，假设循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2^n 也就是说当循环 log2^n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：**O(logn)** ##### **线性对数阶O(nlogN)** 线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n \* O(logN)，也就是了O(nlogN)。 就拿上面的代码加一点修改来举例： ``` for(m=1; m<n; m++) { i = 1; while(i<n) { i = i * 2; } } ``` ##### **平方阶O(n²)** 把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。 ``` for(x=1; i<=n; x++) { for(i=1; i<=n; i++) { j = i; j++; } } ``` ##### **立方阶O(n³)**、**K次方阶O(n^k)** 参考上面的O(n²) 去理解就好了，O(n³)相当于三层n循环 #### **空间复杂度** ##### **空间复杂度 O(1)** 如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1) ``` int i = 1; int j = 2; ++i; j++; int m = i + j; ``` 代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1) ##### **空间复杂度 O(n)** ``` int[] m = new int[n] for(i=1; i<=n; ++i) { j = i; j++; } ``` 第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)