一个算法在特定输入上的运行时间是指执行的基本操作数或步数。首先我们假设执行一行代码需要常量时间。常量时间是指:无论输入规模如何变化,执行这一行代码的时间都不受输入规模的影响。...我们记第 i 行代码的执行时间为 CiC_iCi。
在用插入排序举例之前,我们先看下该算法的基本思想:每步将一个待排序的元素,按其值的大小插入前面已经排序的序列中适当位置上,直到全部元素插入完为止。...例如,对于插入算法来说,若输入数组已排好序,则出现最佳情况。这时,对每个 i=1,2,3,...,n−1i = 1,2,3,...,n-1i=1,2,3,......最坏情况与平均情况分析
在分析插入排序时,我们同时研究了最坏情况和最佳情况。然而我们往往集中于最坏情况运行时间,即规模为n的所有输入中,算法运行时间最长的情况。...我们也忽略最重要的项的常系数,因为对大的输入,在确定计算效率时常量因子不如增长率重要。对于插入排序,当我们忽略掉低阶项和最重要的项的常系数时,只剩下最重要的项中的因子n2n^2n2。