时间复杂度和空间复杂度
时间复杂度
用于评估执行程序所消耗的时间，可以估算出程序对处理器的使用程度。
常用「大O符号表示法」，即 T(n) = O(f(n))，表示时间复杂度。
常见的时间复杂度量级有「复杂度越来越大」：
- 常数阶 O(1)
- 对数阶 O(logN)
- 线性阶 O(n)
- 线性对数阶 O(nlogN)
- 平方阶 O(n²)
- 立方阶 O(n³)
- K次方阶 O(nk)
- 指数阶 O(2n)
常数阶
0(1) 复杂度算法也称之为常数阶算法。这里的 1 是用来代指常量，也就是说这个算法的效率是固定的，无论你的数据量如何变化，效率都一样，这种复杂度也是最优的一种算法。
public static void print(int n){
int a = 1;
System.out.println(a);
}
上面的示例中不论有多少行代码，时间复杂度都是属于常数阶。
换言之：只要代码不存在循环，递归等循环类调用，不论代码有多少行，其复杂度都是常数阶。
对数阶
O(logn) 也称之为对数阶，对数阶也很常见，像二分查找、二叉树之类的问题中会见到比较多的对数阶复杂度，但是对数阶也是比较难理解的一种算法复杂度。
public static void print(int n){
int i=1;
while (i <= n) {
i = i * 2;
}
}
这段代码最关键就是要分析出 while 循环中到底循环了多少次，我们观察这个循环，发现 i 并不是逐一递增，而是不断的翻倍：1->2->4->8->16->32->64 一直到等于 n 为止才会结束，所以我们得到了这样的一个公式：2^x=n。
也就是我们只要计算出 x 的值，就得到了循环次数，而根据高中的数学知识我们可以得到 x=log2N，所以根据上面线性阶的分析方法，我们省略常量，就得到了示例中的算法复杂度为 O(logN)。
线性阶
O(n) 复杂度算法也称之为线性阶。
public static void print(int n){
int a = 0;
for (int i=0;i<n;i++){
System.out.println(i);
}
}
这段代码，for循环里面的代码会执行 n 遍，因此它消耗的时间是随着 n 的变化而变化的，因此这类代码都可以用 O(n) 来表示它的时间复杂度。
线性对数阶
如果理解了上面的对数阶，那么这种线性对数阶就非常好理解了，只需要在对数阶的算法中再嵌一层循环就是线性对数阶：
for (int j=1;j<=n;j++){
int 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 进行表示。
空间复杂度比较常用的有：
- O(1)
- O(n)
- O(n²)
空间复杂度 O(1)
如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)
int i = 1;
int j = i * 5;
代码中的 i、j 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 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)
