复杂度分析笔记
复杂度主要分为时间和空间复杂度
时间复杂度：算法（程序）执行的时间变化趋势
空间复杂度：算法（程序）执行的内存空间使用量
复杂度分析，不是通过工具测量计算出来的，而是估量算法运行所要消耗的时间
通过代码来练习代码复杂度分析
int cal(int n){
int sum = 0;
int i = 1
for(; i < n; i++){
sum = sum + i;
}
return sum;
}
假设每行代码的执行时间都是一样的，unit_time;
再来看这段代码：
第2，3行只执行了一遍，需要时间为2*unit_time
第4，5行执行了n+n编，需要时间为2n*unit_time
所以这段代码需要的总时间T(n) = (2n + 2) * unit_time
再看如下这段代码
int cal(int n){
int sum = 0;
int i = 1;
int j = 1;
for(;i<n;i++){
for(;j<n;j++){
sum = sum + i*j;
}
}
return sum;
}
第2，3，4行执行了一遍 3*unit_time
第5行，执行了n遍，n*unit_time
第6，7行，2n^2
所以这段代码需要的总时间为T(n) = (3+n+2n^2)*unit_time
可以看出来所有的代码的执行时间和每行代码执行的次数成正比
T(n) = O(f(n))
其中的f(n)为代码执行次数的函数
O(n)函数表示代码执行时间与代码执行次数f(n)成正比
这种方法称为大O表示法，并不表示算法执行的具体时间，而是表示随着数据规模增长的变化趋势
随着数据规模不断增大，常数对对时间的影响可以忽略不记
所以上面的两个时间复杂度可以表示为O(n) O(n^2)
时间复杂度分析的几种方法
1.只关注循环 次数最多的那一段代码：
int cal(int n){
int sum = 0;
int i = 1
for(; i < n; i++){
sum = sum + i;
}
return sum;
}
如同上面举过的例子
这里执行次数最多的是第4，5行，其它行数为常数，可以忽略不记，所以这段代码的时间复杂度为O(n)
2.加法法则：总的复杂度等于量级最大的那段代码的复杂度
int cal(int n) {
int sum_1 = 0 ;
int i = 1;
for(;i < n; i++){
sum_1 = sum_1 + i;
}
int sum_2 = 0;
int j = 1;
for(;i < n; i++){
for(;j < n; j++){
sum_2 = sum_2 + i*j;
}
}
return sum_1 + sum_2;
}
可以把这段代码分为两部分来看
第一部分 时间复杂度为O(n)
第二部分时间复杂度为O(n^2)
总的时间复杂度，我们取那个最大的，所以时间复杂度为O(n^2)
换算为公式：T(n) = max(O(f(n)),O(g(n)));
3.乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
int cal(int n){
int sum = 0;
int i = 1;
for(;i < n; i++){
sum = sum + f(i);
}
return sum;
}
int f(int n){
int sum = 0;
int i = 1;
for(;i < n; i++){
sum = sum + i;
}
return sum;
}
上面这段代码，如果f(n)是一段普通的操作，则时间复杂度为O(n)
但是，f(n)不是一份简单的操作，他是一段函数 ，所以总的时间复杂度
T(n) = O(n) * O(n) = O(n^2
需要注意的几点
1.O(1)
O(1)表示时间复杂度为常量，并不是说只有一行代码。即使代码有成千上万行，只要是常数，就记为O(1)
int i = 0;
int j = 1;
sum = i + j;
上面那段代码为O(1)而不是O(3)
2.O(logn) O(nlogn)
int i = 1;
while( i <= n){
i = i * 2;
}
计算上述代码的时间复杂度，关键是计算出来代码执行的次数
2^x = n 所以x = log2 n
所以上述时间复杂度为O(log2n)
采用大O计数法，忽略次数，记为O(logn)
3.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;
}
上述代码，因为m,n的值未知，不清楚谁大谁小,不能省略其中的一个，无法使用加法法则
时间复杂度为O(m + n),
可以使用乘法法则：O(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]
}
}
可以看到上述代码：
只有在第3行的时候才使用了n大小的数组，其余地方都没有使用多余的空间，所以这段代码的空间复杂度为O(n).
