一个算法在特定输入上的运行时间是指执行的基本操作或步数量。
简单来说就是执行每行()伪代码所需演的时间()。
接下来看下面这段伪代码
即运行时间为T(n) =
若输入数组已经排好序,则出现最佳情况
该运行时间表示为an+b
若输入数组已反向排序,则导致最坏情况。此时
该运行时间表示为a+bn+c
接着我们做一些更简化的抽象,我们真正感兴趣的是运行时间的增长率或增长量级。所以我们只考虑公式中最重要的项(例:a),因为当n很大时,低级项相对来说不那么重要。
所以我们记插入排序的最坏运行时间O()