7 then largest ← r
//与右孩子比较，不满足堆的条件
8 if largest ≠ i
9 then {exchange A[i] ↔ A[largest]
10
MAX-HEAPIFY(A, largest)
}
每层比较2次，整理时间与i的高度成正比。
整理堆的实例
有n个节点的堆，最大整理时间为 2 log n。 粗略分析建堆的时间为 n log n，但似乎太不精确了。
只能在规模为n的某些或某类有代表性的合法输 入中统计相应的ei , i=1,2,…,k，评价时间复杂 性。
一般只考虑三种情况下的时间复杂性，即最坏情况、最好情况和平均 情况下的时间复杂性，井分别记为：
W(n) = max{ T(n，I) } , I∈Dn B(n) = min { T(n，I) }, I∈Dn A(n)＝∑P( I )T(n，I) I∈Dn
flag ←0
/*发生了交换*/
} if flag then beak
/* 没有交换，排序结束*/
}
enddo
如果将if a[j]<a[j+1] then {….. }当做一个元运算，花的时间为C
当输入的数据已经排好序，做了n-1次元运算； 当输入的数据是增序，则需要做n(n-1)/2次元运算。
显然，不可能对规模n的每一种合法的输入I都去 统计ei(n,I),i=1,2,…,k。因此T(n,I)的表达式还 得进一步简化。
k
T (N , I ) ti.ei (N.I ) i 1
其中ti，i=1,2,..,k,是与N,I无关 的常数。
先看一个实例：
改进冒泡如排序算法的基本步骤如下：
for i ←1 to n-1 do
{flag ←1
for j ←1 to n-i do
if a[j]<a[j+1] then {交换a[j]、a[j+1]
考察实例的
建堆过程，
总体比较时间 为所有节点的 整理时间之和， 各层上的节点 的整理时间是 相同的。
BUILD-MAX-HEAP(A)
else U← m-1 }
规则7
对于break语句。为了便于表达从循环体的中途跳转到循环 体的结束,引入break 语句。在时间复杂性分析时可以假设 它不需要任何额外的时间。
规则8 对于过程调用和函数调用语句，它们需要的时间包括两部分，
一部分用于实现控制转移，另一部分用于执行过程(或函 数)本身，这时可以根7)进行分析，一层一层地剥，直到计算出 最外层的运行时间便是所求。
如果过程(或函数)出现直接或间接的递归调用，则根据过程(或函数)的内涵建 立起这些待定函数之间的递归关系得到递归方程。最后用求递归方程解 的渐进阶的方法确定最坏情况下的复杂性的渐进阶。
经验和技巧是非常重要的
例：建最大堆算法的复杂性分析
BUILD-MAX-HEAP(A) 1 heap-size[A] ← length[A] 2 for i ← ⌊length[A]/2⌋ downto 1 n/2次 3 do MAX-HEAPIFY(A, i) 归结到分析 MAX-HEAPIFY(A, i)的时间
Dn是规模为n的合法输入的集合，P(I)是在算法的应用中 出现输入I 的概率。
最具有可操作性和实际价值的是最坏情况下的时间复杂 性。我们对算法的时间复杂性分析的兴趣主要将放在W(n) 上。没有特殊说明时，T(n)一般指的就是W(n)。
2.2.1算法时间复杂性计量
对于同一类问题，采用这类算法的基本运算次数作为算法的运算时间。 例如：
MAX-HEAPIFY(A, i)
1 l ← LEFT(i)
2 r ← RIGHT(i)
3 if l ≤ heap-size[A] and A[l] > A[i ] //与左孩子比较，不满足堆的条件
4 then largest ← l
//记下较大者的下标
5 else largest ← i
6 if r ≤ heap-size[A] and A[r] > A[largest]
“汉诺塔”算法的基本运算是圆盘的移动； 比较排序算法，用算法所用的比较次数作为该类算法的 运算时间； 矩阵相乘：基本运算是两个数的相乘； 树的搜索：基本运算是节点的访问； 图的算法：节点和边的运算。
2.2.2 时间复杂性的计算规则
分析时间复杂性渐近阶的8条规则 ： 规则1：
赋值、比较、算术运算、逻辑运算、读写单个常量 或单个变量等，只需要1个单位时间。 规则2 条件语句"if C then S1 else S2"需要Tc+max(Ts1，Ts2)的 时 和间Ts2，分其别中是T执c是行计语算句条S1件和表S达2需式要C的需时要间的。时间，而Ts1 规则3 选择语句"Case A a1:S1; a2:S2; … ;am:Sm; end"， 需要max(Ts1, Ts2，…，Tsm)的时间，其中Tsi是执行语 句Si所需要的时间，i=l,2,…,m。
规则6与规则5不同，循环次数是隐含的。 例如，b_search函数中的while循环语句。按规
则(1)-(4)， while (not found)and(U≥=L)
{m←(U+L) div 2 if c=A[m] then found←true else if c>A[m] then L← I+1
规则4
访问一个数组的单个分量或一个记录的单个域， 只需要1个单位时间。
规则5
执行一个for循环语句需要的时间等于执行该循 环体所需要的时间乘上循环的次数。
规则6
执行一个while循环语句“while C do S”，需要 的时间等于
(计算条件表达式C的时间+执行循环S体的时间)* 循环的次数。
2.1时间复杂性函数
T(N,I) 是算法在一台抽象的计算机上运行所需的时间。 设此抽象的计算机所提供的元运算有k种，他们分别 记为O1,O2 ,..,Ok；设这些元运算每执行一次所需要 的时间分别为t1,t2,..,tk 。
对于给定的算法A，用到元运算Oi的次数为ei， i=1,2,..,k ，很明显，对于每一个i， ei是n和I的函数， 即ei=ei(n,I)。那么有：