时间复杂度和空间分析

算法效率分析分为两种：一是时间效率，二是空间效率。时间效率被称为时间复杂度，而空间效率被称为空间复杂度。时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间。

1.概念
定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。
2.大O的渐进表示法
计算一下Func1基本操作执行了多少次？

void Func1(int N)
{
      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=10;
      while(M--)
      {
           ++count;
       }
       printf("%d\n",count);
 }

Func1执行的基本操作次数：
F（N）=N^2+2*N+10
实际中我们计算时间复杂度不一定要计算精确的执行次数，而只需要大概执行次数，那么我们可以使用大O的渐进表示法。

大O符号：
适用于描述函数渐进行为的数学符号

推导大O阶方法：

1. 用常熟1取代运行时间中的所有加法常数
2. 在修改后的运行次数函数中，只保留最高阶项
3. 如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

使用大O阶的渐进表示法以后，Func1的时间复杂度为：O(N^2)

3.常见时间复杂度计算举例
例1：

void Func2(int N)
{
    int count=0;
    for(int k=0;k<2*N;++K)
    {
         ++count;
     }
     int M=10;
     while(M--)
     {
          ++count;
     }
     printf("%d\n",count);
 }

Func2 的时间复杂度为：基本操作执行了2N+10次，通过推导大O阶方法知道，时间复杂度为O(N)

例2：

void Func3(int N,int M)
{
   int count=0;
   for(int k=0;k<M;++k)
   {
      ++count;
    }
    for(int k=0;k<N;++k)
    {
      ++count;
    }
    printf("%d\n",count);
}

Func3 的时间复杂度为：O（M+N)

例3：

void Func4(int N)
{
  int count=0;
  for(int k=0;k<100;++k)
  {
    ++count;
  }
  printf("%d\n",count);
 }

Func4 的时间复杂度为：通过推导大O阶方法，时间复杂度为O（1）

例4：

const char * strchr(const char *str,int character);

Func5的时间复杂度为：基本操作执行最好1次，最坏N次，时间复杂度一般看最坏，时间复杂度为O(N)

例5：

void BubbleSort(int *a,int n)
{
   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;
    }
 }

时间复杂度为：基本操作最好执行N次，最坏执行（N*(N+1)/2次，因此时间复杂度为O(N^2)

例6：

int BinarySearch(int *a,int n,int x)
{
   assert(a);
   int begin=0;
   int end=n-1;
   while(begin<end)
   {
     int mid=begin+((end-begin)>>1);
     if(a[mid]<x)
       begin=mid+1;
     else if(a[mid]>x)
       end=mid;
     else
        return mid;
    }
    return -1;
 }

时间复杂度为：O(logN)

例7：

long long Factorial(size_t N)
{
   return N<2 ? N:Factorial(N-1)*N;
}

时间复杂度为：O(N)

例8：

long long Fibonacci(size_t N)
{
 return N<2 ? N:Fibonacci(N-1)+Fibonacci(N-2);
}

时间复杂度为：O(2^N)

1.定义
空间复杂度是一个算法在运行过程中临时占用存储空间大小的量度。计算规则基本跟时间复杂度类似，也用大O渐进表示法。
2.实例

1. 计算BubbleSort的空间复杂度

void BubbleSort(int *a,int n)
{
   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)

2. 计算Fibonacci的空间复杂度

long long *Fibonacci(size_t n)
{
    if(n==0)
        return NULL;
    long long *fibArray=new long long [n+1];
    fibArray[0]=0;
    fibArray[1]=1;
    for(int i=2;i<=n;++i)
    {
        fibArray[i]=fibArray[i-1]+fibArray[i-2];
    }
    return fibArray;
}

空间复杂度为：O(N)

3. 计算阶乘递归Factorial的空间复杂度

long long Factorial(size_t N)
{
  return N<2? N:Factorial(N-1)*N;
}

空间复杂度为：O(N)

（注：部分内容来源网上）

转载自：https://blog.csdn.net/D_4_Y_/article/details/82999091