不考虑计算机硬件和软件有关的因素，仅考虑算法本身效率的高低时，算法的效率只依赖问题的规模（用整数n表示），是问题规模的函数。

事前分析估算方法通过分析问题的规模，求出算法的时间界限函数。时间界限函数一般可以表示为

一个算法通常由控制结构（顺序、选择和循环3种结构）和操作构成，算法的运行时间由两者的综合影响。为了比较同一问题的不同算法，通常从算法中选取对于所研究的问题来说是基本操作的原操作，以该原操作重复执行的次数（也称语句频度）度量算法的时间。一般情况下，算法中原操作重复执行的次数是问题规模n的函数f（n），算法的时间度量记作：

它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。

例1.4　计算1+2+3+…+n的算法如下，分析其时间复杂度。

【解】该算法的基本运算是sum+=i，其语句频度为

该程序段的时间复杂度为O（n），通常称为线性阶。

例1.5　已知n为正整数，计算20+21+22+…2i+…，（2i＜n）的算法如下，分析其时间复杂度。

【解】该算法的基本运算是sum+=i，由题意知，while循环中i的值依次为1，2，4，8，16…，其语句频度为(www.daowen.com)

该程序段的时间复杂度为O（log2 n），通常称为对数阶。

例1.6　已知选择排序算法如下，分析其时间复杂度。

【解】该算法的基本运算是双重循环中最深层的比较或赋值语句。当i=0时，基本运算执行n-1次；当i=1时，基本运算执行n-2次；……当i=n-2时，基本运算执行1次。

其语句频度为时间复杂度只需要取最高阶的项，并忽略常数和系数。该算法的时间复杂度为O（n2）。

例1.7　求两个n×n矩阵的积C=A×B的算法如下，分析其时间复杂度。

【解】该算法是一个三重循环，基本运算为A[i][k]×B[k][j]，语句频度为该算法的时间复杂度为O（n3）。

一般，一个没有循环的算法的基本运算次数与问题规模n无关，记作O（1），称为常量阶；一个只有一重循环的算法的基本运算次数与问题规模n为线性关系，记作O（n），称为线性阶；此外还有平方阶O（n2）、立方阶O（n3）、对数阶O（log2 n）、指数阶O（2n）等。不同的时间复杂度存在如下关系：