数据结构与算法——复杂度（上）
数据结构是计算机存储、组织数据的方式。
算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。
程序员学习数据结构和算法，就是学习操纵数据结构解决问题的方法，就是学习如何更快速度更省空间的解决问题，即学习如何让代码跑的更快，如何让计算机更省存储空间。
什么是时间复杂度和空间复杂度？
时间复杂度表示代码执行时间随数据规模增长的变化趋势。
空间复杂度表示代码运行空间随数据规模增长的变化趋势。
比如这段代码：
int cal(int n) {
int sum = 0;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
sum = sum + i * j;
}
}
return sum;
}从 CPU 的角度来看，这段代码的每一行都执行着类似的操作：读数据-运算-写数据。
所以每一行代码的运行时间可以看做一个单位时间，上面代码的总执行时间T(n)=2n²+n+2个单位时间
我们常常看到的T(n)=O(f(n))就是大O时间复杂度表示法
其中，T(n) 表示代码执行的时间；n 表示数据规模的大小；f(n) 表示每行代码执行的次数总和。因为这是一个函数，所以用 f(n) 来表示。公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。
时间复杂度的分析方法
1.以代码中运行次数最多的为主
比如这段代码:
int cal(int n) {
int sum = 0;
int j = 1;
for (int i = 0; i <= n; i++) {
sum = sum + i;
}
return sum;
}执行时间T(n)=2n+3个单位时间，用大O表示法就是O(n)。
再比如这段代码:
int cal(int n) {
int sum = 0;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
sum = sum + i * j;
}
}
return sum;
}执行时间T(n)=2n²+n+2个单位时间
用大O表示法就是O(n²)
凡是低阶和常量都略去
值得注意的是，不管循环多少次，只要是常量，哪怕是上万次，用大O时间复杂度表示法，也应该把这个循环执行的次数略去。
这里说明O(n)不一定比O(n²)执行时间短，只能说明随着n的扩大，O(n²)增长复杂度越来越高，具体到某一段代码而言，要具体分析。
2.嵌套代码的时间复杂度是内外复杂度的乘积
比如这段代码：
int cal(int n) {
int ret = 0;
int i = 1;
for (; i < n; i++) {
ret = ret + f(i);
}
}
int f(int n) {
int sum = 0;
int i = 1;
for (; i < n; i++) {
sum = sum + i;
}
return sum;
}时间复杂度应该是O(n²)
时间复杂度的分类
时间复杂度分为非多项式量级和多项式量级，NP问题(Non-Deterministic Polynomial, 非确定多项式)
非多项式量级只有两种：和n!
当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法。
常见的多项式时间复杂度
1.常量阶O(1)
比如
int i = 8;
int j = 6;
int sum = i + j;2.线性阶O(n)
int cal(int n) {
int sum = 0;
int i = 1;
for (; i < n; i++) {
sum = sum + i;
}
return sum;
}3.平方阶O(n²)
平方阶就是二重循环
int cal(int n) {
int sum = 0;
for (int i = 0; i <= n; i++) {
int j = 1;
for (; j <= n; j++) {
sum = sum + i * j;
}
}
}4.对数阶O(logn)
i=1;
while (i <= n) {
i = i * 3;
}时间复杂度为
实际上，不管是以 2 为底、以 3 为底，还是以 10 为底，我们可以把所有对数阶的时间复杂度都记为 O(logn)。
因为对数之间是可以互相转换的， 就等于
*
，所以 O(
) = O(C *
)，其中 C=
是一个常量。基于我们前面的一个理论：在采用大 O 标记复杂度的时候，可以忽略系数，即 O(Cf(n)) = O(f(n))。所以，
就等于 O(
)。因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn)。
空间复杂度
例子代码
private void print(int n) {
int i = 0;
int[] array = new int[n];
for (i; i <n; i++) {
array [i] = i * i;
}
for (i = n-1; i >= 0; i--) {
System.print.out(array [i]);
}
}跟时间复杂度分析一样，我们可以看到，第 2 行代码中，我们申请了一个空间存储变量 i，但是它是常量阶的，跟数据规模 n 没有关系，所以我们可以忽略。第 3 行申请了一个大小为 n 的 int 类型数组，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是 O(n)。
我们常见的空间复杂度就是 O(1)、O(n)、O( )，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。
我们以0，1，1，2，3，5，8，13...这样的数列（Fibonacci数列）为例，求第n个数是多少？
递归法：
private int fib(int index){
if(index == 0){
return 0;
}
if(index == 1){
return 1;
}
return getNum(index-1)+getNum(index-2);
}虽然代码很短，但是空间复杂度却是O(n)。
循环法：
int fib(int n){
int a = 1;
int b = 1;
int c = 1;
if (n<2){
return n;
}
while (n>2){
c = a + b;
a = b;
b = c;
n--;
}
return c;
}代码虽然比递归法多不少行，但是其空间复杂度为O(1)。
由此可见，学习数据结构与算法能锻炼我们的逻辑思维能力，提升内功，在写代码时能够看出代码的时间和空间复杂度，写出更快更省的代码。
本专栏将每月更新，欢迎关注，大家一起学习，一同进步。