在开发的时候,我们如何评估一个算法的好坏,如何描述一个算法运行效率的高低呢?通俗一点的表达方法就是程序执行快或慢,但是这只是一种较为宽泛的描述,我们如何直观科学的用的描述它呢?
有同学可能会说,用其运行时间不就可以很好很直观的描述它了。不过,不同的语言,不同的编译器,不同的CPU来说,对程序的处理的时间是不同的,我们无法单单用运行时间来描述某个算法执行效率。另外,当需要处理的数据增长时,算法的基本操作要重复执行的次数也会增长,对于不同的算法的增长的速度也不一样。
数学果然是个不错的工具,为了描述算法的运行时间的增长情况,我们可以用不同数学公式来分析。在计算机科学上,我们是有专门的术语来表征算法的效率,就是今天要和大家一起学习的大O表示法。大O并不是表示算法运行需要多长时间,它表示的是算法运行时间的增速,即算法的运行时间以不同的速度增加,也叫渐进时间复杂度。
我们可以用下面的表达式来表示:
通常主要有以下几种表达式来描述时间复杂度:
- O(1):常量时间
- O(n):线性时间
- O(log n):对数时间
- O(n^2):二次方时间
- O(2^n):指数时间
- O(n!):阶乘时间
每种时间复杂度有所不同,下面我们一起来详细了解这几种时间复杂度。
大O复杂度
O(1)
O(1)表示常量时间复杂度,当给定大小为n的输入,无论n为何值,最后算法执行的时间是个常量。举个例子:
- int func(int n)
- {
- n++;
- return n*2;
- }
上面的程序中,无论输入n的值如何变化,程序执行时间始终是个常量。我们简化处理一下,假如函数中每行语句的执行时间是1,则执行时间的数学表达式:
无论n为多大,最后的执行时间都是2这个固定值。虽然是运行时间为2,但是这里我们也用O(1)来表示,这里的1代表是一个常数。
O(n)
O(n)表示线性时间复杂度,算法的执行时间随着输入n的大小成线性变化。
- int func(int n)
- {
- int sum = 0;
- for(int i=0; i
- {
- sum = sum + i;
- }
-
- return sum;
- }
上面的这个程序中,函数的执行时间随着n的变化成线性的关系。
对于这种可以用线性表达式表示的情况,我们用O(n)来表示。
为什么可以省略掉表达式中的其他系数呢?主要是当n趋近于无穷大时,系数相对于无穷大的n来说可以忽略不计。
O(n^2 )
O(n^2)表示二次方时间复杂度,一个算法的时间将会随着输入数据n的增长而呈现出二次关系增加。
- int func(int n)
- {
- int sum = 0;
- for(int i=0; i
- {
- for(int j=0; j
- {
- sum = sum + i + j;
- }
- }
-
- return sum;
- }
上面的程序中,是个两层循环的程序,函数的执行时间和n是二次方的关系:
对于这种类型的程序,我们可以用O(n^2)表示。不过,循环嵌套除了这种两层循环之外,还会有三层、四层...n层循环,对应的其复杂度就是O(n^3) 、O(n^4)...O(n^n)。
O(2^n)
O(2^n)表示指数复杂度,随着n的增加,算法的执行时间成倍增加,它是一种爆炸式增长的情况。
- int func(int n)
- {
- if(n==0) return 1;
-
- return func(n) + func(n-1)
- }
上面的代码中,有两次递归调用,函数的执行时间就会和输入n成指数的关系。
因此,这里我们可以用O(2^n)表示。
O(log n)
O(log n)表示对数时间复杂度,算法执行时间和n是一种对数关系。这种类型的算法会在执行的过程中,随着程序的执行其完成某个功能的操作步骤越来越少。其中,我们所熟知的二分查找法就是一个很好的例子。比如,下面这个代码在一个有序列表中查找某个值的位置,我们通过二分法进行查找。
- int func(int a[], int size, int num)
- {
- int left = 0;
- int right = size-1;
-
- while(left <= right)
- {
- int mid = (left + right)/2;
-
- if(a[mid] > num)
- {
- right = mid - 1;
- }
- else if (a[mid] < num)
- {
- left = mid + 1;
- }
- else
- {
- return num;
- }
- }
-
- return -1;
- }
在最糟糕的情况下,我们通过二分法拆分x次后,最后一个元素就是我们要找的元素。我们可以得到下面的等式:
函数运行时间可以表示为:
因此,这里我们可以用O(log n)表示。
O(n!)
对于阶乘关系的复杂度,最典型的例子就是旅行商问题。
假设有一个旅行商人要拜访n+1个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径长度为所有路径之中的最小值。
这个问题最简单的方法是通过穷举法列出所有的排列组合。如果有n+1个城市,根据我们数学中学过的排列组合计算方法,可以算出所有组合数为n!,所以这种穷举法对应的时间复杂度也就是O(n!)了。
本文转载自微信公众号「Will的大食堂」,可以通过以下二维码关注。转载本文请联系Will的大食堂公众号。