时间复杂度与空间复杂度
一、时间复杂度
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)
腾讯云开发者
