算法复杂性(续) ●●●●● ●●●● ●●0 计算复杂性的表示符号为“O”(称为“大O”,即算法 的阶号),表示计算复杂性的数量级 例如:一个给定算法的时间复杂性为2n2+2n+5 (1)首先,随着n的增大,2n的增长比较大,而低阶部分增长相对较小。所以, 较低阶函数部分均可忽略不计 (2)最高项n2的系数2也可忽略不计。这是因为如果T=O(n2),那么输入尺寸 增加一位,算法的运行时间变为4倍:如果T=O(2n2)那么输入尺寸增加一位算 法的运行时间也增加为四倍 (3)最后,这个给定算法的时间复杂性可以表示为O(n2)。 好处: 使算法复杂性度量与处理器的运行速度和指令运行时间无关 2212明确地揭示了输入的数据长度对算法复杂性的影响。2021/2/10 算法复杂性（续） ⚫ 计算复杂性的表示符号为“O ”（称为“大O”，即算法 的阶号），表示计算复杂性的数量级 好处： ⚫ 使算法复杂性度量与处理器的运行速度和指令运行时间无关； ⚫ 明确地揭示了输入的数据长度对算法复杂性的影响。 例如：一个给定算法的时间复杂性为 2 2 +2 +5 n n 。 （1）首先，随着 n 的增大，2 2 n 的增长比较大，而低阶部分增长相对较小。所以， 较低阶函数部分均可忽略不计。 （2）最高项 2 n 的系数 2 也可忽略不计。这是因为如果 T=O( 2 n )，那么输入尺寸 增加一位，算法的运行时间变为 4 倍；如果 T=O(2 2 n )那么输入尺寸增加一位算 法的运行时间也增加为四倍。 （3）最后，这个给定算法的时间复杂性可以表示为 O(n 2 )