1： 什么是复杂度：
复杂度也叫渐进复杂度：
包含时间复杂度和空间复杂度用来分析算法执行效率和数据规模之间的关系。
时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。
空间复杂度全称就是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。
2：什么是时间复杂度？
时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。
假设：
所有代码的执行时间 T(n) 与 每行代码的的执行次数 f(n) 成正比
得出最后公式： T（n）= O（f（n））
大 O 时间复杂度实际上并不具体表示代码真正的执行时间，
而是表示代码执行时间随数据规模增长的变化趋势，
所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。
要点：
1：只关注循环执行次数最多的一段代码
一个算法的算时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了。
2： 加法法则：总复杂度等于量级最大的那段代码的复杂度
总的时间复杂度就等于量级最大的那段代码的时间复杂度。
3： 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
当N趋向于无穷大时才有意义，因此没有常数。
3：时间复杂度实战
常量阶O(1)：
比如这段代码，即便有 3 行，它的时间复杂度也是 O(1），而不是 O(3)。
int i = 8;
int j = 6;
int sum = i + j;
对数阶O(logn) 线性对数阶O(nlogn)：
对数阶 与 线性对数阶 时间复杂度非常常见，同时也是最难分析的一种时间复杂度：
i=1;
while (i <= n) {
i = i * 2;
}
//稍微改动为 3
i=1;
while (i <= n) {
i = i * 3;
}
对数阶：程序1：O(log2n) 程序2：O(log3n)
时间上不管是 以2为底 还是 以3位底 我们都可以把所有对数阶的实际复杂度记为 O(logn)
线性对数阶O(nlogn) ： 实际上就行对数阶 循环了n编
3：O(m+n)、O(m*n)
从代码m 和 n 是表示两个数据规模。我们无法事先评估 m 和 n 谁的量级大，
所以我们在表示复杂度的时候，就不能简单地利用加法法则
因此代码的时间复杂度就是 O(m+n)。
我们需要将加法规则改为：T1(m) + T2(n) = O(f(m) + g(n))。
但是乘法法则继续有效：T1(m)*T2(n) = O(f(m) * f(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;
}
4：空间复杂度
空间复杂度全称就是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。
5：空间复杂度实战
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]
}
}
第 2 行代码中，申请了一个空间存储变量 i，
但是它是常量阶的，跟数据规模 n 没有关系，所以我们可以忽略。
第 3 行申请了一个大小为 n 的 int 类型数组，
除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是 O(n)。
我们常见的空间复杂度就是 O(1)、O(n)、O(n2 )，
像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。
，空间复杂度分析比时间复杂度分析要简单很多。
所以，对于空间复杂度，上述的这些内容已经足够了。
网友评论