时间复杂度与空间复杂度

作者：lovevivi

2022-10-19
吉林
本文字数：1551 字
阅读完需：约 1 分钟

@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=Nx=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)

发布于: 刚刚阅读数: 4

原文链接:【http://xie.infoq.cn/article/fc1e890a8c3a07ecfa8298253】。文章转载请联系作者。

lovevivi

关注

还未添加个人签名 2022-10-12 加入

还未添加个人简介

发布

暂无评论

创作场景

时间复杂度与空间复杂度

一、时间复杂度

1.概念

2.大 O 的渐进表示法

3.练习题

1.常规情况

2.特殊情况

二、空间复杂度

1.概念

2.用法

lovevivi

评论