1.时间复杂度
- 推导大O阶
1.用常数1取代运行时间中的所有加法常数；
2.在修改后的运行次数函数中，只保留最高阶项；
3.如果最高阶项存在且不是1，则去除这项的系数。
1.1 常数阶
int n;
scanf("%d",&n);
printf("%d\n",n);
- 算法的执行次数函数
f(n) = 3，根据第一步将常数项3改为1，没有最高阶项，时间复杂度为O(1). - 对于分支结构，无论真假，执行次数都是恒定的，不包含在循环结构中的分支结构时间复杂度均为O(1).
1.2 线性阶
int count = 0;
for(int i=0;i<n;++i){
printf("%d\n",++count);
}
- 循环体中的代码要执行n次，时间复杂度为O(n).
1.3 对数阶
int count = 0;
for(int i=0;i<n;i*=2){
printf("%d\n",++count);
}
-
i = i*2，则有多少个2相乘后大于n，即2^i = n，得到i = log2n。所以时间复杂度为O(logn).
1.4 平方阶
int count = 0;
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
printf("%d\n",++count);
}
}
- 外部循环体要执行
n次内部循环，内部循环是时间复杂度为O(n)的语句，在循环n次，时间复杂度为O(n3)
1.5立方阶
int count = 0;
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
for(int k=0;k<n;++k){
printf("%d\n",++count);
}
}
}
- 由于第一层循环以及第二层循环，需要循环
n^2次第三层循环语句，时间复杂度为O(n3).
总结：循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。
1.6 指数阶
int n;
scanf("%d",&n);
int count = 0;
for(int i=0;i<pow(2,n);++i){
printf("%d\n",++count);
}
- 循环语句要执行
pow(2,n)次，所以时间复杂度为O(2n)
1.7 阶乘
long long factorial(int n){
int res = 1;
for(int i=1;i<n;++i){
res*=i;
}
return res;
}
int n;
scanf("%d",&n);
int count = 0;
for(int i=0;i<factorial(n);++i){
printf("%d\n",++count);
}
循环语句需要执行
n!次，所以时间复杂度为O(n!)练习
int n;
scanf("%d",&n);
int count = 0;
for(int i=0;i<n;++i){
for(int j=0;j<i;++j){
printf("%d\n",++count);
}
}
第一层循环结构需要执行内部循环
n次，内部循环的分别执行1，2，...，n-1次，等差序列求和(1+(n-1))*n/2，n^2/2+n/2，没有加法，不考虑常数，保留最高阶n^2/2，去掉最高阶前的系数，得到时间复杂度为O(n2)常见的时间复杂度所耗时间的大小排序
O(1)<O(logn)<O(n)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)
2.空间复杂度
- 运行完一个程序所需内存的大小
- 程序执行时所需存储空间
1.固定部分：指令空间、数据空间等。
2.可变部分：动态分配内存、递归栈等。
