时间复杂度与空间复杂度_萌新的日常的技术博客_51CTO博客
source link: https://blog.51cto.com/u_15787387/5693626
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
时间复杂度与空间复杂度
精选 原创一、时间复杂度
即时间复杂度计算的是执行次数
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)
二、空间复杂度
即创建变量的个数
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)
- 赞
- 收藏
- 评论
- 分享
- 举报
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK