前言：

       一个物品的好坏，我们可以通过体验、口碑、销量等因素判断。那一个算法的好坏我们怎么判断呢？

一、算法的效率

1、如何衡量一个算法的好坏

       如何衡量一个算法的好坏，比如对于以下斐波那契数列：

long long Fib(int n)
{
    if(n < 3)
    {
        return 1;
    }
    else
    {
        return Fib(n - 1) + Fib(n -2); 
    }
}

       我们可以看出斐波那契数列的递归实现代码非常简洁，但是简洁一定好吗？那该如何衡量其好坏呢？

       答案是：一个好的算法首先要具备正确性，然后是健壮性、可读性，在几个方面都满足的情况下，通过算法的复杂度来评判不同算法的好坏程度。

2、算法的复杂度

算法在编写成可执行程序后，进行时需要耗费时间资源和空间（内存）资源。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

时间复杂度：时间复杂度主要衡量一个算法的运行快慢。

空间复杂度：空间复杂度主要衡量一个算法运行所需要的额外空间。

时间复杂度和空间复杂度有时候是矛盾的。

在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们现在已经不需要再特别关注一个算法的空间复杂度了。

二、时间复杂度

1、时间复杂度的概念

在计算机科学中，算法的时间复杂度是一个函数（是数学里面带有未知数的函数表达式），它定量描述了该算法的运行时间。

一个算法执行所耗费的时间，从理论上说，是算不出来的（因为环境不同，具体运行时间就不同），只有你把程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？虽然可以都上机测试，但是这很麻烦（而且环境很难统一），所以就有了时间复杂度这个分析方法。

一个算法所花费的时间与其花费的时间与其中语句的执行次数成正比例（算法运行时间 = 每条语句的频度 * 该语句执行一次的时间，因为环境很难统一且它与算法无关，所以我们可假设执行每一条语句所需的时间均为单位时间），算法中的基本操作的执行次数，为算法的时间复杂度。

即：找到每条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。

                       算法运行时间 = 每条语句的执行次数

例：请计算Func1中count++语句总共执行了多少次？

#include<stdio.h>
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);
}
int main()
{
  int N = 0;
  scanf("%d", &N);
  Func1(N);
  return 0;
}

Func1执行的基本操作次数：

       F（N）= N^2 + 2*N +10

        N = 10           F(N) = 130

        N = 100         F(N) = 10210

        N = 1000       F(N) = 1002010

我们发现N越大，后面两项对结果的影响就越小，所以我们在实际计算时间复杂度时，我们并不需要计算精确的执行次数，只算个大概执行次数就可以了。那这里我们使用大O的渐进表示法（估算）。则Func1的时间复杂度：F（N）= O（N^2）——它不是执行N方次，它是属于N方次这个量级。

2、大O的渐进表达式

       （1）大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。

       （2）推导大O阶方法：            

①用常数1取代运行时间中的所有加法常量。

②在修改后的运行次数函数中，只保留最高阶项。

③如果最高阶项存在且不是1，则去除与这个项相乘的常数（系数），最后得到的结果就是大O阶（是估算值，表示它的量级）。

     （3）一般情况下时间复杂度计算时未知数都是用的N，但是也可以用M，K等等其他。如果某个算法的有两个未知数M和N，那它的大O阶怎么算呢？

①M >> N ——> O(M)

②M << N ——> O(N)

③M和N差不多大 ——> O(M)或O(N)

④没有说明M和N大小关系 ——> O(M + N)

    （4）有些算法中基本操作执行次数还随着问题的输入数据集不同而不同，所以时间复杂度存在最好、平均和最坏情况：

①最坏情况：任意输入模式的最大运行次数（上界）

②平均情况：任意输入规模的期望运行次数

③最好情况：任意输入规模的最小运行次数（下界）

       注意： 当一个算法随着输入不同，时间复杂度不同，时间复杂度做悲观的预期，看最坏的情况！

    （5）递归的算法：递归次数 * 每一次递归调用的次数（最好的理解是画递归图）。

    （6）注：我们算时间复杂度，不能只去看是几层循环，而是去看他的思想！！！

3、常见时间复杂度计算

实例1：计算Func2的时间复杂度

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

答案是：O(N)

解析：Func2的基本操作次数：F(N) = 2N +10,使用上面我们所讲的推导大O阶方法 —— ①用常数1取代运行时间中的所有加法常数，F(N) = 2N + 1；②在修改后的运行次数函数中，只保留最高项，F(N) = 2N；③如果最高项存在且不是1，则去除与这个项相乘的常数（系数），最后得到的就是Func2的大O阶：O(N)。

实例2：计算Func3的时间复杂度

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

答案是：O(M + N)

解析：Func3基本执行了M +N次，有两个未知数M和N —— 因为不知道M和N的大小关系，所以Func3的大O阶：O(M + N)

实例3：计算Func4的时间复杂度

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

答案是：O(1)

解析：Func4基本执行了100次，使用推导的大O阶方法 —— Func4的大O阶：O(1)。注意这里的O(1)不是代表算法就运行一次，而是常数次。

实例4：计算my_strchr的时间复杂度（模拟strchr库函数，strchr是在字符串中查找一个字符）

const char* my_strchr(const char* str, int character)
{
  while (*str)
  {
    if (*str == character)
    {
      return str;
    }
    else
    {
      str++;
    }
  }
  return NULL;
}

答案是：O(N)

解析：该算法中基本操作执行次数还随着问题的输入数据集不同而不同，所以存在：

       ①最好情况：执行一次，即字符串第一个字符就是我们查找的字符 —— O(1)

       ②最坏情况：执行N次（我们一般用N来代表字符串的大小），即在字符串中找不到我们查找的字符 —— O(N)

又因为时间复杂度做悲观预期，所以看最坏的情况，即my_strchr的大O阶：O(N)。

实例5：计算BubbleSort的时间复杂度

//使用冒泡实现整形数组的升序
void BubbleSort(int* a, int n)
{
  //断言指针的有效性
  assert(a);
  //趟数控制一趟冒泡排序要进行多少对比较
  //①外层for循环：趟数 —— 有n个元素，要进行i(i = n - 1)趟
  for (size_t end = n; end > 1; --end)
  {
    //变量：交换，每次冒泡排序开始赋初值0
    int exchange = 0;
    //一趟：一趟比较i - 1对元素
    for (size_t i = 1; i < end; ++i)
    {
      //升序
      if (a[i - 1] > a[i])
      {
        int tmp = a[i];
        a[i] = a[i - 1];
        a[i - 1] = tmp;
        exchange = 1;//发生交换
      }
    }
    //判断是否冒泡排序了，如果没有发生交换，就说明已经提前排序完成
    if (exchange == 0)
    {
      break;
    }
  }
}

答案是：O(N^2)

解析：该算法中基本操作执行次数还随着问题的输入数据集不同而不同，所以存在：

       ①最好情况：基本操作执行了N-1次，即只执行了一趟冒泡，就排序成功 ——O(N)

       ②最坏情况：基本操作执行了N*(N-1)/2，即执行了N-1趟冒泡，才排序成功 ——O(N^2)

因为时间复杂度做悲观预期，所以看最坏的情况，所以BubbleSort的大O阶：O(N^2)

注意：我们算时间复杂度，不能只去看是几层循环，而是去看他的思想！！！

实例6：计算BinarySerrch的时间复杂度

//使用二分查找(也叫折半查找)在有序的整形数组中，查找是否存在x，
//存在则返回该值在数组中的下标。不存在则返回-1。
int BinarySearch(int* a, int n, int x)
{
  assert(a);
  int begin = 0;//开始：下标为0
  int end = n - 1;//结束：下标为n-1
  // [begin, end]：begin和end是左闭右闭区间，因此有=号
  while (begin <= end)
  {
    int mid = begin + ((end - begin) >> 1);//找到数组的中间位置
    if (a[mid] < x)
    {
      begin = mid + 1;
    }//判断x是否大于中间位置，是则需要改变开始位置
    else if (a[mid] > x)
    {
      end = mid - 1;
    }//判断x是否小于中间位置，是则需要改变改变结束位置
    else
    {
      return mid;
    }//最后就是相等，找到，返回该值的下标
  }
  return -1;//找不到，返回1
}

答案是：O(logN) ——（因为对数的底数在键盘在难写，所以在时间复杂度这里我们可以这样简写）

解析：该算法中基本操作执行次数还随着问题的输入数据集不同而不同，所以存在：

在有序的情况下，二分查找是一个非常牛逼的算法，直观的看看它有多厉害：

N个数中查找                        大概查找次数

1000                                        10（2^10 =1024）

100w                                        20（2^20 = 1024*1024）

10亿                                         30（2^30）

但是在在平时我们却不常使用，因为它必须满足有序的情况，后期我们会讲到红黑树，它的时间复杂度与二分一样。

实例7：计算阶乘递归Fac的时间复杂度

long long Fac(size_t N)
{
  if (0 == N)
  {
    return 1;
  }//递归出口
  else
  {
    return Fac(N - 1) * N;
  }//每一次递归调用之后，越来越接近递归出口
}

答案是：O(N)

解析：递归的算法：递归次数 * 每一次递归调用的次数 —— 画Fac的递归图如下：

实例8：计算斐波那契数递归Fib的时间复杂度

long long Fib(size_t N)
{
  if (N < 3)
  {
    return 1;
  }//递归出口
  else
  {
    return Fib(N - 1) + Fib(N - 2);
  }//每一次递归调用后，越来越接近递归出口
}

答案是：O(2^N)

解析：递归算法：递归次数 * 每一次递归调用的次数 ——画Fib的递归图如下：

斐波那契数的递归算法完全是一个没用的写法，因为效率太慢了，所以我们一般改写为迭代的写法。

三、空间复杂度

空间复杂度也是一个数学表达式，是对一个算法在运行过程中额外临时占用存储空间大小的量度。

空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是额外创建的变量的个数。空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。

注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显示申请的额外空间来确定。

实例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])
      {
        int temp = a[i - 1];
        a[i - 1] = a[i];
        a[i] = temp;
        exchange = 1;
      }
    }
    if (exchange == 0)
      break;
  }
}

答案是：O(1)

解析：从上述代码我们可以看见变量end、i、exchange、temp以及数组a和变量n。我们根据空间复杂度的定义，空间复杂度算的是额外创建的变量的个数的量级。数组a和变量n不是为了排序额外创建的，变量end、i、exchange、temp是为了排序而额外创建的。所以使用了4个即常数个额外空间，所以空间复杂度为O（1）。

实例2：计算Fibonacci的空间复杂度？

// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{
  if (n == 0)
  {
    return NULL;
  }
  long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));
  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)

解析：空间复杂度算的是显示申请的额外创建的变量的个数的量级，看上述代码最大的量级就是malloc动态开辟了N + 1个空间，所以空间复杂度为O(N)。

实例3：计算阶乘递归Fac的空间复杂度？

long long Fac(size_t N)
{
  if (N == 0)
  {
    return 1;
  }
  return Fac(N - 1) * N;
}

答案是：O(N)

解析：如下图

实例4：计算斐波那契数递归Fib的空间复杂度

long long Fib(size_t N)
{
  if (N < 3)
  {
    return 1;
  }//递归出口
  else
  {
    return Fib(N - 1) + Fib(N - 2);
  }//每一次递归调用后，越来越接近递归出口
}

答案是：O(N)

解析：（1）递归就是函数在定义是有直接或间接调用自身的方法，思想就是大事化小。递归通常有两个必要条件，①递归出口；②每一次递归调用后，越来越接近递归的出口。（2）递归要把两个字分开理解：①递——递推，递推到递归出口停止，每一次递推都会调用自身函数，即会在栈区创建函数栈帧；②归——回归，函数栈帧销毁，将内存还给操作系统。（3）如下图：

1、内存的申请和销毁就像生活中的酒店（注意：内存的销毁是把内存还给操作系统）。

2、递归的空间复杂度算法：递归开辟的不一样的栈帧个数* 每一个递归使用空间的个数（最好的理解是画递归图）

3、为什么递归的时间空间复杂度不一样：因为时间是一去不复返的，不可重复利用，但是空间用了以后可以归还，可以重复利用。

四、常见复杂度

一般算法常见的复杂度如下：

练习1链接：面试题 17.04. 消失的数字 - 力扣（LeetCode）

题解：

   法1：异或：相同为0，不同为1（注：①操作数为整数；②是针对二进制位）。

时间复杂度为O(N)。

       法2：公式计算：0~n的和（等差：Sn = （a1 + an）* n / 2） - 数组的值。时间复杂度为O(N)。

法1代码演示：

int missingNumber(int* nums, int numsSize)
{
    int val = 0;//创建变量来异或得到缺失的数，初始化为0,0与任意数异或得到任何数
    //①先与输入异或
    int i = 0;
    for(i = 0;i < numsSize;i++)
    {
        val ^= nums[i];
    }
    //②再与0~n异或，得到缺失的数
    for(i = 0;i < numsSize + 1;i++)
    {
        val ^= i;
    }
    return val;
}

法2代码演示：

int missingNumber(int* nums, int numsSize)
{
    int sum = numsSize * (numsSize + 1) / 2;//0~n的和
    //for遍历，减去数组的值
    int i = 0;
    for(i = 0;i < numsSize; i++)
    {
        sum -= nums[i];
    }
    //返回缺失的数
    return sum;
}

练习2链接：189. 轮转数组 - 力扣（LeetCode）

题解：

法1：开辟额外的空间，以空间换时间——建立一个与原数组一样大的新数组，把k个元素，拷贝到新数组的前面，再把新数组拷贝到原数组中，返回即可。

时间复杂度：O(N)，空间复杂度：O(N)

  法2： 翻转数组

时间复杂度：O(N),空间复杂度：O(1)

法1代码演示1：在栈区创建于原数组一样大的新数组

void rotate(int* nums, int numsSize, int k)
{
    int newArr[numsSize] ;//创建的新数组
    int i = 0;//循环变量
    //将k个元素拷贝到新数组中
    for(i = 0;i < numsSize;i++)
    {
        newArr[(i + k) % numsSize] = nums[i];
    }
    //再把新数组拷贝到原数组
    for(i = 0;i < numsSize;i++)
    {
        nums[i] = newArr[i];
    }
}

法1代码演示2：在堆区动态创建一块与数组一样大的空间

void rotate(int* nums, int numsSize, int k)
{
    //特殊情况：当k>numsSize是
    if(k > numsSize)
    {
        k %= numsSize;
    }
    //动态创建一块numsSize的连续空间
    int* tmp = (int*)malloc(sizeof(int)*numsSize);
    //判断是否开辟成功
    if( NULL == tmp)
    {
        return ;
    }
    //将后k个元素拷贝到前面
    memcpy(tmp,nums + numsSize - k,sizeof(int) * k);
    //将前numsSize-k个元素拷贝到后面
    memcpy(tmp + k,nums,sizeof(int)*(numsSize - k));
    //最后将tmp指向的内容拷贝回原数组
    memcpy(nums,tmp,sizeof(int) * numsSize);
    //释放
    free(tmp);
    tmp = NULL;
}

法2代码演示：翻转数组

//reverse函数实现逆置整形数组
void reverse(int* nums,int begin,int end)
{
    while(begin < end)
    {
        //交换
        int tmp = nums[begin];
        nums[begin] = nums[end];
        nums[end] = tmp;
        ++begin;
        --end;
    }
}
void rotate(int* nums, int numsSize, int k)
{
    //特殊情况：当k>numsSize是
    if(k > numsSize)
    {
        k %= numsSize;
    }
    //调用reverse函数逆置数组时，注意传的是下标
    //①前n-k个逆置
    reverse(nums,0,numsSize - k - 1);
    //②后k个逆置
    reverse(nums,numsSize - k,numsSize - 1);
    //③整体逆置
    reverse(nums,0,numsSize - 1);
}