复杂度分析
在学习算法之前首先要明确一个衡量算法优劣的概念，算法的复杂度。
- 时间维度：是指执行当前算法所消耗的时间，通常用
时间复杂度来描述；- 空间维度：是指执行当前算法所需要占用的内存空间，通常用
空间复杂度来描述。
时间复杂度计算---算法的渐进时间复杂度： T(n) = O(f(n))
举个例子：
for (int i=0; i<n; i++) { a++; b++; }对于这个例子，假设每行代码执行的时间都是
1单位时间，那么第一行消耗1单位，第二行和第三行每次消耗1单位，循环n次，那么就总共消耗n+n单位时间，所以该例子中，总的时间为：T(n) = (1+2n) 单位时间可以看出，该算法的耗时是随着n变化而变化的，与其他变量无关，就可以将该算法的时间复杂度表示为
O(n)。
注意：这里的时间复杂度并不等价于表示算法的执行时间，只是用来表示代码执行时间的增长变化趋势。在实际情况中一般关注算法的最坏运行情况。
常见的时间复杂度量级：
- 常数阶
O(1)
- 算法内没有循环等复杂结构。
- 线性阶
O(n)
- 单层循环，代码执行n遍。
- 对数阶
O(logN)
- 在循环中，循环结束条件以乘法的形式递增，例如
while(i<n) i=i*2，i距离n是越来越近的，设循环x次后退出，那么2的x次方=n,x=log2n，所以复杂度简化为：O(logN)- 线性对数阶
O(nlogN)
- 将时间复杂度为O(logN)的算法循环n次。即有两层循环。
- 平方阶
O(n²)
- 循环嵌套，都是O(n)，从这可以推出O(n^k)
他们的大小关系：
O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n2)平方阶 < O(n3)(立方阶) < O(2n) (指数阶)
空间复杂度：类似时间复杂度，不是具体计算程序实际占用空间，是对一个算法在运行过程中临时占用存储大小的一个度量，常见的有S(n) = O(1), O(n), O(n²)
- O(1)表示临时空间不随着某个变量n的变化而变化。
- O(n)，分配了n个大小的存储空间
