数据结构与算法：算法效率

博客大纲

数据结构与算法简介

什么是算法

算法(Algorithm):就是定义良好的计算过程，它取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。

对于算法而言，语言并不重要，重要的是思想。但是，对于程序开发而言，语言非常重要。不论你习惯于哪一种编程语言，在算法上的学习都是相似的。在此我以C/C++来进行讲解。

什么是数据结构

数据结构是指相互之间存在着一种或多种关系的数据元素的集合

也就是说数据之间不是独立的，存在特定的关系，这些关系即结构。

数据结构与算法的关系

1.数据结构是底层，算法高层；

2.数据结构为算法提供服务；

3.算法围绕数据结构操作；

以上关系可以理解为：

数据是算法操作的对象，算法的功能是基于其对象的。没有数据，算法就无法实现价值。而没有算法，数据会凌乱，不可控。

我们可以根据不同的数据来使用最优算法，当然也有好的算法具有十分强的普适性，可以用在多种数据。

这两者不可分割，所以这里几乎无法把它们分开讲解。

数据结构与算法的重要性

对于大部分程序员而言，算法在工作中不是必须的，但是你要找工作，特别是刚毕业参加校招的学生，想进入一些比较大的公司，是必须要学好算法的。

比如在招聘网站上的大厂要求：

以及一些学长学姐在面试时遇到的问题：

算法效率

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

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

时间复杂度

时间复杂度的定义:

在计算机科学中，算法的时间复杂度是一个函数（数学意义上的），它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗?是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度

（引入）实例一：

试求下列代码count++执行次数：

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

在第一个i与j循环中，count的执行次数与N有关。最终的执行次数为n²。

第二个循环中，执行了2n次

第三个循环中执行了10次

那么最终这个count语句执行的次数就是：

F(N) = N² + 2N + 10 （此处的F(N)就是一个时间复杂度的函数）

这就是此算法时间复杂度了吗？

并不！

计算机的计算效率是非常高的，计算效率都是以每秒几亿次为单位来评估的。所以在评估一个算法的计算效率的时候，需要把这个N想成一个无限大的数字。因为n=10与n=10000，对计算机来说都是一样的。就像一个亿万富翁，亏损10块钱和亏损1w块钱，对他造成的影响都是微乎其微的。

那我们这样的精确计算就是多余的，比如刚刚表达式中的常数10完全可以忽略。而当n趋于无穷，我们会发现算法的时间复杂度会越来越接近那个最高次项的值。

这里智慧的先人就发明了大o渐进表示法，用于估算时间复杂度与空间复杂度。

大O渐进表示法：

基本规则：

1：保留最高阶项

2：对于常数以及未知数的系数，用1代替

3：当程序计算次数不确定，以最坏情况计算复杂度

接下来我们就讲解这个规则是如何使用的

在此我们以F(N)作为没有使用大O的时间复杂度，以O(N)作为大O表示后的时间复杂度

在括号中，它可以是任何影响算法效率的变量符号，但在规范中，一般都由N代替。

就像数学中的函数b =a²，一般都会写成y=x²。自变量用x，应变量用y，这是一种规范或是约定俗成。而时间复杂度规范就是复杂度中的变量一般用N表示

注意：大O渐进表示法只用于估算，以上所有步骤都是在排除那些对程序影响不大的因素，使最后得到的复杂度简单，易于理解。这样一个程序员在看到或者估算出算法的时间复杂度的第一时间就知道这个算法效率如何。

对于实例一：

F(N) = N² + 2N + 10

对于上方的第一个算法，保留最高次方N为²，并且其没有系数

那么对于上述的公式，用大O渐进表示后就是O（N²）

接下来我们以几个实例来分析讲解。

（规则1，规则2）实例二:

void Func2(int N)
{
int count = 0;
for (int k = 0; k < 2 * N ; ++ k) //时间复杂度为2N
{
++count;
}
int M = 10;
while (M--)//时间复杂度为10
{
++count;
}
printf("%d\n", count);
}

F(N)=2N+10

此处用先用规则1，保留最高次，就变成了2N

然后规则2，把此项系数改为1，最后时间复杂度就是O(N)。

（变量N规范）实例三：

void Func3(int N, int M)
{
  int count = 0;
  for (int k = 0; k < M; ++k)//时间复杂度为M
  {
    ++count;
  }
  for (int k = 0; k < N; ++k)//时间复杂度为N
  {
    ++count;
  }
}

F(N) = M+N

在此处，时间复杂度同时和两个变量有关，且他们的指数相同。

我们用O(M+N),O(max(M,N))，O(M)，O(N)等来表示，都是可以的。

但是他们都是同一个量级的，也就是变量一次方的量级。到最后规范表示就是O（N）。

如果此处在第一个M的循环外侧再套一个执行M次的循环呢？

void Func3(int N, int M)
{
  int count = 0;
  for (int a = 0; a < M; a++)//时间复杂度为M²
  {
    for (int k = 0; k < M; ++k)
    {
      ++count;
    }
    for (int k = 0; k < N; ++k)//时间复杂度为N
    {
      ++count;
    }
  }
}

F(N)=M²+N

保留最高次M²

大O处理后就是O（M²），由于大O内部一般由字母N（不是此代码中的N）表示，所以规范表示为O（N²）。

(规则2)实例四：

void Func4(int N)
{
  int count = 0;
  for (int k = 0; k < 100; ++k)//时间复杂度为100
  {
    ++count;
  }
  printf("%d\n", count);
}

F(N)=100

此处可以发现，for循环的执行次数与n无关，为固定的100次。那么时间复杂度就是100

依据规则2，此处留下的是常数项，把常数项转为1，那么大O渐进表示后为O（1）。

在上文我提出过，大O渐进的作用是删去那些对运算效率影响不大的因素。此处也是由于计算效率强悍。所以常数个的计算都可以当做不存在，但是这个算法确实产生了额外的计算，于是规定，这里把所有常数都用1表示，1代表这个算法确实产生了一点点额外计算，但是影响微乎其微。

以上四个例子，我用第一个例子引入大O渐进表示法，再用了三个例子讲解前两条规则，接下来我们讲解第三条规则。

算法运行次数不确定的时间复杂度计算：

const char* strchr(const char* str, int character)
{
  while (*str)
  {
    if (*str == character)
      return str;
    str++;//执行次数不确定
  }
  return NULL;
}

这是一个在字符串中查找字符的函数，当这个函数找到了字符，就返回指针偏移量，否则返回NULL。

我们不细讲此函数。但是可以看到，在if语句中，只要对比字符相同就停止计算，不然就执行一次计算++str，对比下一个字符。我们并不知道这个字符在字符串的什么位置，那我们也就不清楚这个算法计算几次++str，这种情况就要使用规则三。

依据规则三，在不确定算法执行次数的时候，要以最坏情况来计算。那此处怎么才算最坏情况？

那就是这个字符出现在字符串的最后一个（++str执行strlen（str）-1次）

或者说这个字符根本不在字符串中（++str执行strlen（str）次）

那么这个算法的计算次数就和strlen（str）有关，最坏情况就是F（strlen（str））

用大O渐进表示并规范后就是O（N）。

在此我们就讲完了时间复杂度计算的三个规则，我们来点习题练习一下，并讲解一些特殊情况。

冒泡排序的时间复杂度（循环内有多次计算，或同一循环体内每次计算次数不同）：

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

这里，冒泡排序分为两个循环，外侧循环用于控制每次排序多少个数字，内侧循环用于排序。

算法的计算量都在内测循环，虽然每次内侧循环会进行多次计算，甚至因为循环内有if语句，有可能一次循环中不计算，这该怎么是好？

对于大O渐进表示法，如果循环内出现计算次数有多次，以每次循环以只计算一次来算。

解释：

假设算法每次循环执行3条计算语句，那么我们的时间复杂度就是F(N) = 3N，大O渐进表示就是O(N)

假设算法每次循环执行1条计算语句，那么我们的时间复杂度就是F(N) = N，大O渐进表示就是O(N)

看吧，由于大O渐进表示法会改系数为1，所以不论循环内有多少计算语句，都以执行一条计算来算

也就可以推导出，就算每次循环内执行的计算语句不相同，也可以按每次循环内只计算一次来算。

后续在面对循环内有多个计算语句的时候，我也会用“计算一次”这个说法，但实际上并非只计算一次，我只是默认这个规则的使用。

对于大O渐进表示法，出现循环偶尔不计算，以每次循环以只计算一次来算。

解释：

假设在上述循环中，每一次if都成立，那么我们的时间复杂度就是F(N) = N-1,大O渐进表示就是O(N)

假设在上述循环中，只有一次if不成立，那么我们的时间复杂度就是F(N) = N-2,大O渐进表示就是O(N)

这个地方，由于循环虽然出现不计算情况，但是这个情况在计算时间复杂度时会被转化为一个常数，常数在此会被省略，导致最后的大O渐进表示不变。

当然你也可以按照规则3：按照最坏的情况来计算，进行推导，也就是每次if都成立。

也就是说我们只要计算出内侧循环执行了多少次，就可以得到时间复杂度。

可见，内侧循环的执行次数是一个等差数列，用求和公式得到F(N)= (n-1)(n-1+1)/2 = n(n-1)/2

利用大O渐进法表示法，去除系数以及非最高次项，得到O(N²)

二分查找的时间复杂度(logN类型)：

int BinarySearch(int* a, int n, int x)
{
  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 - 1;
    else
      return mid;
  }
  return -1;
}

由于规则3，我们计算时间复杂度按照最坏情况，也就是找到最后一个元素才找到，或者找完整个数组都没找到。

二分查找算法中，每执行一次计算，就会把数组长度减半。当数组长度被减为1，那么这个算法就结束了。

数组长度为变量N，设进行了x次计算，每次计算N长度减半，目标是让长度N减为1。

可得算式N/2^x=1,变形后得到x = logN

（计算机中由于log以2为底数的对数出现过于频繁，于是规定以log表示以2为底的对数，这样既不会与数学中的lg重复，也方便输入）

X就是计算次数，也就是时间复杂度F(N) = logN,得到O(logN)

与递归有关的时间复杂度计算:

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

每次递归的计算是并列关系，递归的时间复杂度是每次调用的计算量的累加

对于上述函数，我用一张图片描述：

可以看到，每次递归都执行一次乘法计算，此处共执行了N次，每次的计算量相加，得到的就是时间复杂度F(N) = N,大O渐进表示就是：O(N)

递归形式斐波那契数列时间复杂度计算（进一步理解估算思想，以及规范）

long long Fib(size_t N)
{
  if (N < 3)
    return 1;
  return Fib(N - 1) + Fib(N - 2);
}

以上是一个斐波那契数列的递归代码，接下来我们进行解析，求其时间复杂度

以下是递归示意图：

图片解释：

对于此递归，它每一层递归都会比上一层多出两倍的计算量。但是递归的结束条件是Fib(2)或者Fib(1)。由于右侧的Fib，参数小于左侧，它会先结束递归。

比如左下角这一段图片，在前面某次递归得到Fib(3)和Fib(4)后，Fib(3)由于参数小，先结束了递归，只有Fib(4)到达了指数为n-2的层次。

在此我用一块阴影表示没有递归到的区域

但是由于我们的大O渐进法只进行估算，这块区域几乎可以忽略不计，任然以这个等腰三角形的面积计算。

计算：

由于每一层递归都是上一层的两倍，左侧指数从0开始到n-2结束，所以共n-1层。

此结构图可以视为一个等比数列，公比为2，首项为1，共有n-1项。

用等比数列求和公式得到F(N) = 2^(n-1)-1

那么，大O渐进表示为O(2^N)还是O(2^N-1)？答案是O(2^N)

理解1：

大O渐进表示的是变量本身与时间复杂度的关系，这个变量用N来表示，这里这个变量N-1就可以视为是一个变量，规范表达后就是N。

理解2：

2^N-1 = 1/2 * 2^N，也就是说可以理解为变量前面有一个系数1/2，它会在执行规则2时被修改。

空间复杂度

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

空间复杂度不是程序占用了多少byte或bit的空间，空间复杂度算的是新建变量的个数。

空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。

新建变量：对于一个算法，它所在的程序必然有自己的变量，但是有时候算法本身会需要新建一些变量，只有这些算法内部创建的变量才计入空间复杂度。

空间复杂度的大O渐进表示法与先前几乎没有区别，只是作用对象变成了新建立的变量个数。

有了先前的基础，空间复杂度会十分容易理解。

在此就不赘述空间复杂度的大渐进表示法，重点讲解两种复杂度在大O渐进表示法下的区别。

冒泡排序的空间复杂度

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

上述代码中，创建了exchange变量，并且在一个循环內部。

那它的空间复杂度就是O(N)咯？

其实并不是，只有当变量同时出现，才能算多个空间复杂度。

在此处，exchange的生命周期是外层的for循环，当外层for循环进入下一次循环，上一次创建的exchange就会销毁。

也就是说多个exchange变量不会同时出现，只占用了一块空间

进一步理解时间复杂度与空间复杂度在循环中的区别：

时间复杂度就是算法占用时间，空间复杂度就是算法额外空间

我们将其类比为住酒店，一个人住酒店，需要预定居住时间，酒店也要为其分配房间。

对于循环时间复杂度：

相当于一个人住酒店结束后，另外一个人入住，他们虽然用了相同的房间，但是总共消耗的时间是累加的

故时间复杂度在循环中是要多次计算的

对于循环空间复杂度：

相当于一个人住酒店结束后，另一个人入住，他们使用了相同的房间，对酒店来说，没有消耗额外的房间。

故对空间复杂度，若多个变量没有同时存在，不额外计算空间复杂度

一般形式斐波那契数列的空间复杂度计算（理解空间复杂度与变量类型无关）

注意：此处为斐波那契数列的另一种实现方法，此方法没有使用递归。

long long* Fibonacci(size_t n)
{
  if (n == 0)
    return NULL;
  long long* fibArray = (long long*)malloc((n + 1) * sizeof(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;
}

此代码使用了malloc开辟了空间，共开辟了n+1个longlong类型变量。

这里不论开辟的空间是int，long还是longlong，空间复杂度只看变量个数，不看类型，都是一样的。

所以空间复杂度就是F(N) = N-1，大O渐进表示为O(N)

递归形式斐波那契数列空间复杂度计算（理解递归函数的空间开辟）

long long Fib(size_t N)
{
  if (N < 3)
    return 1;
  return Fib(N - 1) + Fib(N - 2);
}

函数在调用的时候，会创建一块空间，在递归时，会调用函数，就会创建新的空间，当一个函数执行到return，才会销毁该函数使用的空间。

在上上题我们讲过，空间复杂度要看同时出现的变量个数。那么函数递归的调用，难道是所有函数同时调研吗？

并非如此，函数递归是单线程的，并非每一层的函数同时执行。下方是错误的理解：

递归正确调用思路：

当一个函数执行完，才会返回上一层函数，在递归的时候，进入下一层函数的同时，原本函数的空间并不会销毁，因为还没有执行到return。

也就是说，函数递归时会顺着一条路递归到底，到底部的函数执行了第一个return，才开始销毁函数空间。

上图绿色箭头代表创建空间给函数，红色箭头代表函数空间销毁。

可以看到，最后调用Fib(2)与Fib(1)并不是同时占用的内存，也就是说他们只算一个空间复杂度。

那么类推出来，就是每一层函数，占用同1块空间，只是占用先后的问题。

这里有n-1层，那么空间复杂度就是F(N) = N + 1，大O渐进后就是O(N).。

带有复杂度限制的oj题分析

复杂度的分析，在程序编写中，其实是第一步，并非写完代码后再去评判一个代码的好坏。

思路1：

先利用排序算法，将数组排序（假设利用冒泡排序）

然后从头开始，num与num+1匹配，如果num+1不是下一项，那么说明下一项就是缺失的数字

复杂度分析：此处利用冒泡排序上方已经分析过，冒泡排序的时间复杂度为O(N²)

思路2：

利用异或找“单生狗”

引入两个公式：

a ^ a = 0

a ^ 0 = a

定义一个a = 0

然后把a和所有0-n的数字进行异或，再把a和所有数组中的元素异或

如果一个数字在0-n和数组中共出现两次，就会触发第一个公式，导致这个数字变成0

而那个“单生狗”，也就是消失的数字（miss_num），只异或了一次

导致最后执行第二个公式a = miss_num ^ 0 = miss_num

也就是说到了最后，a就已经是那个消失的数字了

复杂度分析：此处使用数字a = 0，遍历了一遍数组（N-1），然后遍历了0-你的数字（N）

所以F(N) = 2N -1，O(N)

思路3：

由于0-n是一个已知的连续的数字串

我们可以利用等差数列前n项和公式求出0+1+2+…+n

然后把这个总和减去数组中的所有元素

这个算法，求前n项和计算了一次，遍历数组一一相减计算了N次

所以时间复杂度就是O(N)

在此我就不把代码一一展示了，算法的重点是思路。

通过上述分析，并非想要教懂大家一道题，而是告诉大家，我们不敲代码，也是可以分析出一个算法的复杂度。

以后在写程序的时候，不妨多想几个思路，然后利用思路分析复杂度，从而选最好的算法。