算法的时间复杂度用什么计量?

C

算法执行时间的度量不是采用算法执行的绝对时间来计算的,因为一个算法在不同的机器上执行所花的时间不一样,在不同时刻也会由于计算机资源占用情况的不同,使得算法在同一台计算机上执行的时间也不一样,另外,算法执行的时间还与输入数据的状态有关,所以对于算法的时间复杂性,采用算法执行过程中其基本操作的执行次数,称为计算量来度量。算法中基本操作的执行次数一般是与问题规模有关的,对于结点个数为 n 的数据处理问题,用 T(n) 表示算法基本操作的执行次数。为了评价算法的执行效率,通常采用大写 O 符号表示算法的时间复杂度,大写 O 符号给出了函数 f 的一个上限。其它义如下: 定义: f (n)=O (g (n)) 当且仅当存在正的常数 c 和 n 0 ,使得对于所有的 n≥n 0 ,有 f (n) ≤c g(n) 。 上述定义表明,函数 f 顶多是函数 g 的 c 倍,除非 n 小于 n 0 。因此对于足够大的 n ( 如 n≥n 0 ) , g 是 f 的一个上限(不考虑常数因子 c )。在为函数 f 提供一个上限函数 g 时,通常使用比较简单的函数形式。比较典型的形式是含有 n 的单个项(带一个常数系数)。表 1-1 列出了一些常用的 g 函数及其名称。对于表 1-1 中的对数函数 logn ,没有给出对数基,原因是对于任何大于 1 的常数 a 和 b 都有 log a n =log b n/log b a, 所以 log a n 和 log b n 都有一个相对的乘法系数 1/log b a ,其中 a 是一个常量。

算法A的时间复杂度等于算法B