关于时间复杂度

Author: 张浩森 Date: Feb 11, 2018 Updated On: Feb 21, 2018
Categories:
Tags: algorithm

一个好的算法应该具备时间效率高且要求存储量低的特点。这里只记录时间效率的衡量的方式。今年12月份-明年1月份左右就要考研了。这里记录的大部分可能针对考研中的算法时间复杂度分析。

对于时间复杂度的分析,我们只要牢记一句话,就能把定义搞明白:将算法中基本操作的执行次数作为算法时间复杂度的度量。这里讨论的时间复杂度不是执行完一段程序的总时间,而是其执行基本操作的总次数。所以时间复杂度指的是次数值,而不是一个时间长度。而这里的基本操作,在我目前的知识水平理解来,可以包括赋值、运算(加减乘除等等)、函数调用等等。因此,对一个算法进行时间复杂度分析的要点,无非是明确算法中哪些操作是基本操作,然后计算出基本操作重复执行的次数即可。在一个算法中,总能找到一个n,可以称为问题的规模,如果要处理的数组元素的个数为n,那么基本操作所执行的次数是n的一个函数f(n)(这里的函数是数学函数的概念,不是编程语言中的函数的概念)。对于求其基本操作执行的次数,就是求函数f(n)。求出以后就可以取出f(n)中随n增大而增长最快的项,然后将其系数变为1,作为时间复杂度的度量,记为T(n) = O(f(n)中增长最快的项/此项的系数)。例如,f(n) = 2n^3 + 4n^2 + 100,则其时间复杂度为T(n) = O(2n^3/2) = O(n^3)。实际上计算算法的时间复杂度就是给出相应的数量级,当f(n)与n无关时,时间复杂度为T(n) = O(1);当f(n)与n是线性关系时,T(n) = O(n);当f(n)与n是平方关系时,T(n) = O(n^2);以此类推。

总结一下,求一个算法的时间复杂度可以分为以下几个步骤:

1、明确算法的问题规模,明确算法中的基本操作。

2、基于算法的问题规模计算算法中执行基本操作的次数,即计算f(n)。

3、找出f(n)中增长最快的项,除以系数,即可求出T(n) = O(n)。

注意:有的算法中基本操作的执行次数不仅跟初始输入的数据规模有关, 还和数据本身有关。例如,一些排序算法,同样有n个待处理数据,但数据初始有序性不同,则基本操作的执行次数也不同。因此排序算法中时间复杂度分为最佳情况、平均情况和最差情况。因此一般依照使得基本操作执行次数最多的输入来计算时间复杂度,即将最坏的情况作为算法时间复杂度的度量。

常见的时间复杂度有:

常数阶O(1) < 对数阶O(log2n) < 线性阶O(n) <线性对数阶O(nlog2n) < 平方阶O(n^2) < 方阶O(n^3) < k次方阶O(n^k) < 指数阶O(2^n) < O(n!) < O(n^n)

例子1:

求出以下算法的时间复杂度

1
2
3
4
5
6
7
8
9
viod fun(int n)
{
int i = 1;
int j = 100;
while(i < n){
j++;
i+=2;
}
}
第一步:找出基本操作,确定规模n。

1)找出基本操作。基本操作即以求时间复杂度为目的的前提下,重复执行次数和算法的执行时间成正比的操作。通俗的说,这种操作组成了算法,当它们都执行完的时候算法也结束了,多数情况下取最深层循环内的语句所描述的操作为基本操作,显然本例中j++与i+=2这两行都可以作为基本操作。

2)确定规模。由循环条件i < n可知,循环执行的次数(基本操作执行的次数)和参数n有关,因此参数n就是我们所说的规模n。

第二步:计算出n的函数f(n)。

显然,n确定以后,循环的结束与否和i有关。i的初值为1,每次自增2,假设i自增m次后循环结束,则i最后的值为1 + 2m,因此有1 + 2m + K = n(其中K为一个常数,因为在循环结束时i的值稍大于n,为了方便表述和进一步计算,用K将1 + 2m修正成n,因为K为常数,所以这样做不会影响最终时间复杂度的计算),解得m = (n - 1 - K)/2,即f(n) = (n - 1 - K)/2,可以发现其中增长最快的项为n/2,因此时间复杂度T(n) = O(n)。

例子2:

分析一下算法的时间复杂度

1
2
3
4
5
6
7
8
9
void fun(int n)
{
int i;
int j;
int x = 0;
for(i = 0; i < n; i++)
for(j = i + 1; j < n; j++)
x++;
}

分析:

x++处于最内层循环,因此取x++作为基本操作。显然n为规模,可以算出x++的执行次数为f(n) = n * (n - 1) / 2,变化最快的项为n^2/2,因此时间复杂度为T(n) = O(n^2)。

例子3:

1
2
3
4
5
6
7
8
9
void fun(int n)
{
int i = 0;
int s = 0;
while(s < n){
i++;
s += i;
}
}

分析:

显然规模为n,基本操作为i++和s += i,i与s都从零开始,假设循环执行m次结束,则有s1 = 1,s2 = 1 + 2 = 3,s3 = 1 + 2 + 3 = 6,……,sm = m(m + 1)/2(其中sm为执行到第m次的时候s的值),则有m(m + 1)/2 + K = n(K为起修正作用的常数),由求根公式得,m = [-1 + 根号下(8n + 1 - 8K) ]/2,即f(n) = [-1 + 根号下(8n + 1 - 8K) ]/2。因此时间复杂度为T(n) = O(根号n)。

三条总结:

1、取决于执行次数最多的语句,如当有若干个循环语句时,算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。

2、如果算法的执行时间不随着问题规模n的增加而增长,即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)

3、算法的时间复杂度不仅仅依赖于问题的规模,还与输入实例的初始状态有关。