1.3.3 算法效率的衡量方法 又如何估算算法的时间复杂度呢? 任何一个算法都是由一个"控制结构"和若干"原操作"组成的,因此一个算法的执行时间可以看成是所有原操作的执行时间之和 ∑( 原操作(i)的执行次数 原操作(i)的执行时间 ) 则算法的执行时间与所有原操作的执行次数之和成正比。 从算法中选取一种对于所研究的问题来说是基本操作的原操作,以该基本操作在算法中重复执行的次数作为算法时间复杂度的依据。这种衡量效率的办法所得出的不是时间量,而是一种增长趋势的量度。它与软硬件环境无关,只暴露算法本身执行效率的优劣。下面举三个例子介绍时间复杂度的估算方法。 |
"原操作"指的是固有数据类型的操作,显然每个原操作的执行时间和算法无关,相对于问题的规模是常量。同时由于算法的时间复杂度只是算法执行时间增长率的量度,因此只需要考虑在算法中"起主要作用"的原操作即可,称这种原操作为"基本操作",它的重复执行次数和算法的执行时间成正比。 |