如何分析算法的时间复杂度?算法的时间复杂度仅与问题规模相关吗?

如何分析算法的时间复杂度?算法的时间复杂度仅与问题规模相关吗?

假如将算法中基本操作的重复执行次数看成是问题规模72的某个函数ƒ(n)，算法的渐近时间复杂度记作：T(n)=O(ƒ(n))。它表示随问题规模n的增大，算法执行时间的增长率和ƒ(n)的增长率相同，其中ƒ(n)一般为算法中频度最大的语句频度。在分析算法时，往往对算法的时间复杂度和渐近时间复杂度不予区分，而经常是将渐近时间复杂度T(n)=O(ƒ(n))简称为时间复杂度。由于算法的时间复杂度考虑的只是对于问题规模n的增长率，则在难精确计算基本操作执行次数(或语句频度)的情况下，只需要求出它关于n的增长率或阶即可。不同的计算机系统执行一次基本操作的时间是千差万别的，不能用一个统一的量来衡量。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数(n)，算法的时间量度记为：T(n)=O(ƒ(n))。所以，不能说算法的时间复杂度仅与问题规模相关。