算法复杂度基本知识

1.基本概念.
时间复杂度： 当前算法所消耗的时间。
空间复杂度： 当前算法所消耗的空间。
评价一个算法的好坏主要看这个算法的时间复杂度和空间复度。
2.时间复杂度. 「 大O符号表示法 」，即 T(n) = O(f(n)) ，其中f(n)表示每行代码执行次数之和，而O表示正比例关系。
例子：

for(int i=1; i<=n; ++i)
{
   j = i;
   j++;
}

假设每行代码的执行时间都是一样的，用1颗粒时间来表示，
那么这行代码第一行耗时1个颗粒时间， 第三行执行时间为n倍的颗粒时间，第四行为n倍的颗粒时间。
总时间T(n)=(2n+1)倍的颗粒时间，当n无线大的时候，2倍和加1就没有意义了。
常用的时间复杂度量级有：
*
常数阶O(1)
*
对数阶O(logN)
*
线性阶O(n)
*
线性对数阶O(nlogN)
*
平方阶O(n²)
*
立方阶O(n³)
*
K次方阶O(n^k)
*
指数阶(2^n)

从上到下时间复杂度越来越大，效率越来越低。
3.空间复杂度
空间复杂度是一个算法在运行过程中临时占用空间大小的一个度量。用S(n)度量。

int[] m = new int[n]
for(int i=1; i<=n; ++i)
{
   j = i;
   j++;
}

第一行new n个空间出来，后来的循环并没从新分配内存空间。
一般时间复杂度是一个上限，空间复杂度不会超过时间复杂度。