时间复杂度简单算
湖北省大冶市第一中学 姚申峰
时间复杂度在《数据结构》一书中是这样描术的：一般情况下，算法中基本操作重复执行的次数是问题规模的的某个函数，算法的时间量度记作，表示随问题规模的增大，算法执行时间的增长率和的增长率相同；其中“”的形式定义为：若是正整数的函数，则表示存在一个正的常数M，使得当时满足。从这段描述中，学生很难理解，如果换一下说法就容易多了。就是所用时间函数、执行次数函数这两函数当整型自变量趋向于无穷大时，两者的比值是一个不等于0的常数。很显然问题重复执行次数和算法的执行时间是成正比的，只要得到语句的频度就能得到时间复杂度。
下面就以几个具体的例子来求解时间复杂度。
例1：Temp=i；
i=j；
j=temp；
以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作。
如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是。
例2： i=1； ①
while(i<=n)
i=i*2； ②
其中语句①的频度是1 ，设语句②的频度,则有：，即
所以该程序段的时间复杂度
例3： x=0；y=0； ①
for(k=1；k<=n；k++) ②
x++； ③
for(i=1；i<=n；i++) ④
for(j=1；j<=n；j++) ⑤
y++； ⑥
其中语句①的频度是2；语句②的频度是n+1；语句③的频度是n；语句④的频度是n+1；语句⑤的频度是n*(n+1)；语句⑥的频度是n2。所以频度之和为f(n)=n2+5n+4
当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度决定的。
一般情况下，对循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分。因此，以上程序段中频度最大的语句是⑥，其频度为，所以该程序段的时间复杂度为。
常见的时间复杂度，按数量级递增排列依次为：常数阶、对数阶、线性阶、线形对数阶、平方阶、立方阶、k次方阶、指数阶，显然，时间复杂度我们尽可能选用多项式阶的算法，而不希望用指数阶的算法，因其效率极低，其算法也就不可取的。
常见的时间复杂度，按数量级递增排列依次为：常数阶、对数阶、线性阶、线形对数阶、平方阶、立方阶、k次方阶、指数阶，显然，时间复杂度我们尽可能选用多项式阶的算法，而不希望用指数阶的算法，因其效率极低，其算法也就不可取的。
本文发表于（NOI导刊）
