时间复杂度和空间复杂度
PS：近日，微信公众号流量主开通条件由原来的5000粉丝降至500粉丝，还记得微信的口号是：“再小的个体也有自己的品牌”，相信之前犹豫未开通公众号的也会在今后的一段时间内开通，当然，腾讯这么做也是因为现在的公众号打开率非常低，而且还有面对百度、头条等对信息流的掌控，不变是不行的。
时间复杂度和空间复杂度可以帮助我们根据具体的平台选择合适的算法，要学会以空间换时间或以时间换空间的设计思想，如在单片机等一般是内存空间比较紧张，在追求最优算法时应该可以适当以时间来换空间进行设计，当然在大内存设备上可以选择以空间换时间的设计思想来设计最优算法，所以，时间和空间复杂度可在一定的限制条件下作为判断某个算法或代码块运行快慢的判断方式，主要从如下几个方面了解和学习时间和空间复杂度：
数据结构与算法关系
时间复杂度
空间复杂度
总结
数据结构与算法关系
数据结构指一组数据的存储结构，而算法是操作数据的一组方法，所以数据结构为算法服务，算法作用于特定的数据结构。
数据结构与算法关系
大O复杂度表示法
大O复杂度表示法可以粗略的了解代码运行的时间效率，比如下面这段代码：
int cal(int n) {
int sum = 0;
int i = 1;
for (; i <= n; ++i) {
sum = sum + i;
}
return sum;
}
假如有效代码（有赋值操作）每一行的执行时间为一个单位时间，那么上述代码的执行时间可表示为 2n + 2 个单位时间，这里可以看出代码执行时间与每行有效代码执行的次数成正比。
如果是下面这段代码：
int cal(int n) {
int sum = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
j = 1;
for (; j <= n; ++j) {
sum = sum + i * j;
}
}
}
在假设条件下上述代码的执行时间可表示为 2n*n + 2n + 3，这里也可以看出代码执行时间与每行有效代码执行的次数成正比，使用公式可表示为：
T(n) = O(n)
则上述两段代码执行时间与代码执行次数之间的关系可以表示为：
T(n) = O(2n + 2)
T(n) = O( 2n*n + 2n + 3)
随着数据规模的增大，后面的常数项不会影响代码执行时间随数据规模增长的变化趋势，上面两个函数很明显一个是线性函数，一个是二次函数，随着 n 的增大，最终二次函数的值会超过一次函数，所以我们取最高阶来作比较，去除其他的次要向，简化后如下：
T(n) = O(n)
T(n) = O(n*n)
现在就可以说上述两段代码的时间复杂度用大O表示法可表示为 O(n) 和 O(n*n)。
时间复杂度
时间复杂度：从上面得出的结论，我们知道使用大O表示法表明的是该段代码执行时间随数据规模增大的变化趋势，大O表示法的假设前提是随着数据规模的增大，只保留最高阶项就能估算代码运行的时间复杂度，所以在进行复杂度分析时，只关注量级最大的时间复杂度即可。
常见的时间复杂度量级从小到大依次是：
常数阶(O(1)) < 对数阶(O(logn)) < 线性阶(n) < 线性对数阶(O(nlogn)) < 平方阶(O(n^2)) < 立方阶(O(n^3)) < 阶乘阶(O(n!)) < n次方阶(O(n^n))
上面的量级中阶乘阶、次方阶都属于非多项式量级，当数据规模急剧增大时，非多项式量级算法执行时间越来越长，这种算法也是最低效的算法，下面说明一下多项式量级的注意点。
O(n)：无论有多少行代码，只有执行次数能确定，那么它的时间复杂度量级就表示为 O(1)，不会出现 O(2)、O(3)等其他情况。
O(logn)：对数时间复杂度计算主要是找到满足的条件，计算代码运行的次数，即代码运行多少次才能执行完，举例如下：
i=1;
while (i <= n) {
i = i * 2;
}
如上述代码，我们只要知道这段代码执行多少次执行完就可以了，也就是找到 i 与 n 的关系，i 的值依次是 1、2、8、16 等，也就是 2^0、2^1、2^3、2^4等，所以 i 与 n 的关系 2^t = n，然后计算出 t 的再剔除无关项的时间复杂度就是对数时间复杂度。当然线性对数阶 O(nlogn) 就是将上述代码循环 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;
}
m 和 n 表示两个数据规模，我们无法确定 m 和 n 谁的量级大，此时的时间复杂度就表示为 O(m) + O(n)，如果 sum_1 * sun_2 则相应的时间复杂度表示为 O(m) * O(n)。
时间复杂度分析基本如上，下面来继续看一下如下特殊情况复杂度分析，分析一下下面代码的时间复杂度：
// n 表示数组 array 的长度
int find(int[] array, int n, int x) {
int i = 0;
int pos = -1;
for (; i < n; ++i) {
if (array[i] == x) pos = i;
}
return pos;
}
分析过程：i 和 pos 的赋值操作共 2 次，不会影响代码执行时间随数据规模增大的趋势变化可忽略，在 for 循环中，如果 i 增加到 m 的时候，满足 for 循环里面的 if 语句中的条件，则此时的时间复杂度表示为 (1+m)n，所以该段代码的事件复杂度一定是 O(n)，因为 if 语句在找到与 x 相等的值的时候还是没有退出 for 循环，修改代码如下：
// n 表示数组 array 的长度
int find(int[] array, int n, int x) {
int i = 0;
int pos = -1;
for (; i < n; ++i) {
if (array[i] == x) {
pos = i;
break;
}
}
return pos;
}
如果在找到数组中与 x 的值相等的值就退出循环，此时对于事件复杂度 (1+m)n 就有两种可能，一种是能找到符合 if 语句条件的值退出循环，此时 m 一定是常量值可以忽略，此时这段代码的复杂的就是 O(1)，当然如果已知不满足 if 语句的判断条件，一直循环 n 次，此时这段代码的事件复杂度还是 O(n)，可见同一段代码在不同的条件下可能会有不同的时间复杂度，鉴于这种情况，将时间复杂度细化为三种：
最好情况时间复杂分析：指理想情况下执行某段代码的复杂度，对应上述代码就是当在数组中找到满足 if 语句条件的值的时候，上述代码的时间复杂度就是 O(1) 就是最好时间复杂度；
最坏情况时间复杂分析：指最糟糕情况下执行某段代码的复杂度，对应上述代码就是永远在数组中找不到满足条件的退出 for 循环，此时上述代码的时间复杂度就是 O(n) 就是最坏时间复杂度；
空间复杂度
空间复杂度反映的是存储空间随数据规模增长趋势，如下面这段代码：
void print(int n) {
int i = 0;//栈内存
int[] a = new int[n];//堆内存
for (i; i <n; ++i) {
a[i] = i * i;
}
}
上面代码中关于内存申请的代码只有两处，其中变量 i 所占内存空间是固定的，忽略不计，其中数组的声明申请了内存，而且大小还是 n 个 int 型所占内存的大小，所以此段代码的空间复杂度为 O(n)。
总结
时间复杂度反映代码执行时间随数据规模增长的变化趋势，重点关注循环嵌套等，空间复杂度反映存储空间随数据规模增长的变化趋势，时间复杂度相较空间复杂度更常用，开发常说的复杂度如果不指定一般说的都是时间复杂度。此外，针对一段特定代码，还可以细化为最好情况时间复杂度、最坏情况时间复杂度、平均时间复杂度和均摊时间复杂度，分析思路基本一样，只是限制条件不同。
推荐阅读：