@TOC
一、时间复杂度
1.概念
在这里插入图片描述即时间复杂度计算的是执行次数
2.大O的渐进表示法
1.用常数1取代时间中的所有加法常数
2.在修改后的运行次数函数中，只保留最高项
3.如果最高项存在而且不是1，则去除与这个项目相乘的常数，得到的结果就是大O阶
3.练习题
### 1.常规情况
void Func1(int N)//Func1的操作次数 { int count=0; for( int i=0;i<N;i++) { for(int j=0;j<N;j++) { count++; } } for(int k=0;k<2*N;k++) { count++; } int M=0; while(M--) { count++; } printf("%d\n",count); }
正常来说，操作次数应为o(N^2)+o(2*N)+o(M)，但是只保留o(N ^2)
但若N为一个很大的数 如100000，平方后为10000000000，
就不会在意后面的几千几百的附加值了
void Fun2(int N)//计算Fun2的操作次数 { int count=0; for(int k=0;k<2*N;k++) { count++; } int M=10; while(M--) { count++; } printf("%d\n",count); }
操作次数为O(2*N)+10，但只保留O(N)
如果N为一个很大的数，如100000，加一个常数区别不大，所以就不需要加上了
同理，一个数的2倍对于本身影响也不是很大，所以也会忽略掉
void fun4(int N)//计算fun4的操作次数 { int count=0; for(int k=0;k<100;k++) { count++; } printf("%d\n",count); }
操作次数为O(1) ，因为100是常数次用1代替
2.特殊情况
void bubblesort(int *a,int n)//冒泡排序 的bubblesort的操作次数 { assert(a); for(size_t end=n;end>0;end--) { int exchange=0; for(size_t i=1;i<end;i++) { if(a[i-1]>a[i]) { swap(&a[i-1],&a[i]); exchange=1; } } if(exchange==0) break; } }
本题也再次证明了并不是所有双for循环都是O(N^2)
,假设有n个数，处于最坏情况下
冒泡排序是先通过第一个数与后面的数依次比较，比较次数为n-1
然后变为第二个数与后面的数比较，比较次数为n-2
直到交换次数为1时完成冒泡排序
操作次数为 1 +2+3+……+n-2+n-1
通过等差数列计算为n(n-1)/2 即 O(N^2)
最好的情况下为有序，执行n-1次就结束了，即O(N)
void binarysearch (int *a,int n, int x)//二分查找的操作次数 { assert(a); int begin=0; int end=n; while(begin<end) { int mid=begin+(end-begin)>>1; if(a[mid]<x) { begin=mid+1; } else if(a[mid]>x) { ned=mid; } else { return mid; } } return -1; }
我们所知道的二分查找，每次都取半，如果mid的值大于想要取得值k
则右边界取mid-1，若mid值小于想要取得值k，则左边界取mid+1
假设元素个数为N个
则 为 N/2/2/2……/2=1
反之为 1* 2* 2 * 2 * 2 …..* 2=N
设x为操作次数 即 2^x=N
x=log 2 N 依照规则忽略 即 O(log N)
long long factorial(size_t N)//阶乘 { return N<2?N:factorial(N-1)*N; }
假设为3时得递归展开图
在这里插入图片描述可以看出当N为3时 ，一共递归了3次，每次递归函数调用一次即时间复杂度为O(N)
二、空间复杂度
1.概念
在这里插入图片描述即创建变量的个数
2.用法
void bubblesort(int *a,int n)//冒泡排序 的bubblesort的空间复杂度 { assert(a); for(size_t end=n;end>0;end--) { int exchange=0; for(size_t i=1;i<end;i++) { if(a[i-1]>a[i]) { swap(&a[i-1],&a[i]); exchange=1; } } if(exchange==0) break; } }
这里的空间复杂度为O(1)
因为变量的个数为常数个，所以在大O的渐进法中为O(1)
long long*fibonacci(sizse_t n) { if(n==0) { return NULL; } long long*fibary=(long long*)malloc((n+1)*sizeof(long long)); fibary[0]=0; fibary[1]=1; for(int i=2;i<=n;i++) { fibary[i]=fibary[i-1]+fibary[i-2]; } return fibary; }
这道题因为malloc动态开辟了n+1个空间
所以空间复杂度为o(n)
