算法复杂度分析是整个数据结构的基础，贯穿整个学科。先放一张xmind图，用以总结
补充一下常见的时间复杂度分析：
当数据规模n越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长，因此非常低效，一句话，根本不能用，因此看几个常见的多项式时间复杂度
- O(1)
int i = 5;
int a = 6;
这段代码的时间复杂度是0(1),不是O(2)。 只要代码执行次数不随着数据规模n的增加而增加，则此代码的时间复杂度就是O(1);
- O(long(n))、 O(nlog(n))
对数阶时间复杂度非常常见，难分析
int i=1;
while (i <= n) {
i = i * 4;
}
上面代码的时间复杂度是㏒4(n);
变换一下
int i=1;
while (i <= n) {
i = i * 8;
}
时间复杂度变为㏒8(n)
因为log之间可以互相转换，比如 ㏒8(n) = ㏒8(4) * ㏒4(n)
而大O表示法又与常数项无关，因此对数阶层的时间复杂度我们舍掉底数，统一表示为O( ㏒n)。
将上面代码执行n遍，就得到时间复杂度nlogn，归并排序和快速排序的时间复杂度都是它。
- O(m+n)、 O(m*n)
如果一个算法的时间复杂度与两个数据规模有关
int cal(int m, int n) {
int sum_1 = 0;
int i = 1;
for (; i < m; ++i) {
sum_1 = sum_1 + i;
}
int sum_2 = 0;
int j = 1;
for (; j < n; ++j) {
sum_2 = sum_2 + j;
}
return sum_1 + sum_2;
}
则算法复杂度为O(m+n),因为无法确定m与n谁更大
空间复杂度
表示算法的存储空间与数据规模之间的增长关系。
void print(int n) {
int i = 0;
int[] a = new int[n];
for (i; i <n; ++i) {
a[i] = i * i;
}
for (i = n-1; i >= 0; --i) {
print out a[i]
}
}
上述代码只有定义数组a时，给a分配了长度为n的空间，其他代码不涉及存储空间的分配，因此该代码的空间复杂度为n
算法复杂度还分为最好情况时间复杂度、最坏情况时间复杂度、平均情况时间复杂度和均摊时间复杂度。
- 最好时间复杂
看一个例子
int find(int array[], int n, int x){
int pos = -1;
for ( int i =0; i<n; i++) {
if(array[i] == x){
pos = i;
break;
}
}
return pos;
}
如果传入的x恰好是数组array的第一个元素，则此时代码执行了一次，为最好情况时间复杂度O(1)，如果传入的x恰好树数组array的最后一个元素，或者根本就不在数组里，则此时情况为最坏时间复杂度O(n)。
那么平均时间复杂度怎么算呢，假设传入的x在数组里与不在数组里的概率都为1/2,那么传入的x在数组里的每个位置的概率就是 1/n * 1/2, 如果在第一个位置，则代码执行1此，如果在第二个位置，代码执行2次，在第n-1个位置就执行n次， 那么一共就需要执行
平均时间复杂度全称应该是叫 加权平均时间复杂度或者期望时间复杂度
