算法基础——复杂度

前言

       算法是解决问题的一系列操作的集合。著名的计算机科学家Niklaus Wirth曾提出：算法+数据结构=程序，由此可见算法在编程中的重要地位。本篇主要讨论算法性能好坏的标准之一——复杂度。 

---

 1 复杂度概述

1.1 什么是复杂度

       本文所讨论的复杂度是指通过事先估算法计算出的用来衡量算法效率的值。因此并不是说代码的长度越长复杂度就越高，或者代码中的数据越多复杂度就越高。

1.2 为什么会有复杂度

       关于复杂度的产生，我们通过下图的问题来引入。假设现在有一个人要从A地前往E地，那么他共有ABE、ADE、ABCE三种路径可以选择，但是我们可以看出，ABE的路程是最短的（假设图中距离与实际距离成比例），经过的地区也是最少的，相较于其它两条路径，ABE的优势非常明显。

       算法是用来解决问题的操作步骤的集合，而我们解决同一个问题可能会如上例一样，有多种路径，这时我们需要一个标准来评判每条路径的好坏。这样一来，算法的复杂度就被提出了。

1.3 复杂度分类

       算法的复杂度分为时间复杂度和空间复杂度两种。

       时间复杂度用来衡量算法消耗时间的多少，空间复杂度用来衡量算法所需开辟新空间的多少。

2 时间复杂度

2.1 什么是时间复杂度

       首先我们要明白，程序运行的绝对时间并不是衡量算法效率的标准。举个不太恰当的例子，使用“ENIAC”计算机（世界上第一台电子数字式计算机）与“天河一号”超级计算机执行相同的算法（死循环除外），它们的绝对时间必然有所不同。

       从中我们得出，当我们评判一个算法的好坏时，不能附带有硬件条件的影响，而应关注算法本身。算法的执行时间的长度可以由每条语句的执行时间乘以该语句的执行次数，再加和得到。而每条语句的单次执行时间对现代计算机来说几乎可以忽略不计，那么对于一个程序的执行时间影响最大的因素就是单条语句的执行次数了。

       因此，时间复杂度主要是用来渐进表示执行次数最多的单条语句的执行次数。

2.2 时间复杂度的计算 

       时间复杂度通常用"O"表示。对于任意输入量n（这里的输入量不一定是数字，也可能为数组或结构变量等，根据具体情况而定），算法的时间复杂度可记作"O(f(n))"，其中f(n)为n的函数，表示算法中的语句的执行次数。但是我们通常会使用渐进表示法来表示时间复杂度，即取f(n)中次数最高的项来表示（当n足够大时，最高次项对整个数值的影响最大）。

       如果仅仅通过这些文字来理解时间复杂度可能较为抽象，我们通过几个简单的例子来理解一下。

int main()
{int a;int i;for(i=0;i<10;i++)a=i;return 0;
}

       我们来看这段代码，这其中代码执行的总次数（即执行的语句数量）为13，为一个常数，我们计这段代码的时间复杂度为"O(1)"。

       这可能与大家的理解有些偏差，明明执行次数为13，为什么不计作"O(13)"呢？我们来观察这段代码，由于这段代码的输入量n对程序的运行次数不会产生影响，那么无论输入量n的大小为多少，这段代码的执行次数都是13。当输入量n趋向于无穷大时，执行次数13与1的区别并不大，可以忽略不计。为方便起见，将这些执行次数为常数的算法的时间复杂度计为"O(1)"。

       也就是说，无论算法的语句执行次数为10,20,30还是一亿，十亿，一百亿，只要它是常数，那么当输入量n趋向于无穷大时，这些常数均可忽略不计，则时间复杂度计为"O(1)"。

int main()
{int a;int n;int i;scanf("%d",&n);for(i=0;i<n;i++)a=i;return 0;
}

       我们再来看这段代码，这段代码与之前的代码相比的不同之处在于其有一个输入量n，并且输入量n会对代码的执行次数产生影响，例如，当输入2时，代码执行次数为7；输入量为10时，代码执行次数为15。可以推出，这段代码的执行次数与输入量n的关系为f(n)=n+5。

在这个关系中，当n趋向于无穷大时，5这个常量可忽略不计，因此我们将这个算法的时间复杂度计为"O(n)"。

       通过对上面两段代码的分析，我们可以总结出一些规律，对比可以发现，影响时间复杂度的主要因素就是循环语句的循环次数与输入量n的关系。在第二段代码中，输入量为n时，循环语句执行n次，则时间复杂度为"O(n)"。

int main()
{int i,j,n;scanf("%d",&n);for(i=0;i<n;i++){for(j=0;j<n;j++){printf("%d ",i*j);}}while(i--){j--;}return 0;
}

       我们继续来看，这段代码中存在嵌套循环语句，当输入量为n时，对于任意一次外层循环，内层循环都进行n次。而外层循环也进行n次，因此总共可认为进行n*n次，即n^2。

       除此之外，这段代码中还存在另一段while循环语句，不难得出循环进行n次，因此这段代码执行的总次数可以计为n^2+n+2。当输入量n趋向于无穷大时，相对于n^2，n+2的值对总次数的影响并不大，可以忽略不计。

       因此，这段代码的时间复杂度计为"O(n^2)"。

2.3 一些经典算法的时间复杂度分析

2.3.1 冒泡排序

      冒泡排序是一种简单的交换排序，通过比较相邻两个元素的大小，若它们的大小顺序与所需顺序不同，则交换这两个元素。这里先不讨论冒泡排序的原理，直接来分析代码。

void BubbleSort(int* a,int sz)
{int i,j;for(i=0;i<sz-1;i++)  //排序次数{for(j=0;j<sz-i-1;j++)  //比较次数{if(arr[j]<arr[j+1])  //判断相邻两数据大小{int tmp = arr[j];arr[j] = arr[j+1];arr[j+1] = tmp;}}}
}

      上面为一段最简单的冒泡排序算法，其中参数a为所需排序的数组的地址，sz为所需排序的元素个数，当给定数组大小为n时，该算法的循环总共进行[(n-1)+(n-2)+...+1]次，化简可得(n^2-n)/2次，因此该算法的时间复杂度计为"O(n^2)"。

2.3.2 二分查找 

      二分查找是一种非常高效的查找算法，可以在一串有序数据中快速查找出所需数据。 

int BinarySearch(int* a,int sz,int x)
{int left=0,right = sz-1;while(left<=right){int mid = (left+right)/2;  //取中间值if(a[mid] == x)   return mid;    //找到与x相等的元素，返回下标else if(x > a[mid])left = mid;   //中间值偏小elseright = mid;  //中间值偏大}return -1;  //查找失败
}

       二分查找算法的最好情况是第一次就找到目标值，此时时间复杂度为"O(1)"。但是我们评判一个算法的好坏不可能凭其处理问题的最好情况时的复杂度作为参考，这是没有意义的。一般来讲，我们会以算法的处理最坏情况的时间复杂度作为该算法的时间复杂度。

      在最坏的情况下，在整个数组中无法找到目标元素。由于二分查找每次取中间值即可排除一半的元素，因此可得当输入量为n时，二分查找总共需要进行大约为以二为底n的对数次，当对数的底数为2时，在表示算法的时间复杂度时，可计为"O(logn)"。

      因此，二分查找的时间复杂度为"O(logn)"。

3 空间复杂度 

3.1 什么是空间复杂度

       我们知道，程序运行时需要调用内存空间，而算法作为程序的一部分，同样也需要调用空间。

       而空间复杂度就是衡量一个算法执行所需调用空间的大小的标准。

       在很多情况下，在评判算法的性能好坏时，空间复杂度的参考权重比时间复杂度要低得多，因此有些算法可能会采取牺牲空间复杂度的方式来换取更低的时间复杂度。但这并不代表空间复杂度不重要。

3.2 空间复杂度的计算 

       空间复杂度的计算和时间复杂度的计算较为相似，在理解了时间复杂度的计算规则后，理解空间复杂度的计算应该会比较轻松。我们还是通过例子来分析。

int main()
{int a;return 0;
}

上面这段代码可以说非常简单了，总共开辟了两块内存空间，一块用来调用main函数，另一块存储变量a。由于开辟的空间大小为常数，因此该段代码的空间复杂度为"O(1)"。

int* copy(int* a,int sz)
{int* ret = (int*)malloc(sizeof(int)*sz);return ret;
}

       这是一个复制函数，用来将给定的数组复制。在这个函数中，当给定数组的大小为n时，该函数会开辟一个大小为n的空间用来复制数组，因此其空间复杂度为"O(n)"。

---

结束语 

       了解复杂度是学习算法的基础，它让我们明白如何判断一个算法的好坏。学会判断复杂度后，我们将会知道如何优化算法，并学会在不同情景下使用最合适的算法。

       以上就是我对复杂度的理解了，如内容有误欢迎各位大佬指正。