时间复杂度与空间复杂度

一、时间复杂度

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);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

正常来说，操作次数应为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);
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

操作次数为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);
 }
1
2
3
4
5
6
7
8
9

操作次数为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;
 }
}
   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

本题也再次证明了并不是所有双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;
}
  
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

我们所知道的二分查找，每次都取半，如果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;
 }
1
2
3
4

假设为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;
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这里的空间复杂度为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;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这道题因为malloc动态开辟了n+1个空间
所以空间复杂度为o(n)