问题:如何比较不同算法的性能?
分析算法的运行时间
算法分析的原则
归纳基本操作 如:运算、赋值、比较
统一机器性能 假设基本操作代价均为1
统一机器性能后,算法运行时间依赖于问题输入规模与实例
相同输入规模,实例影响运行
最好情况:不常出现,不具有普遍性
最坏情况:确定上界,更具一般性 常用最坏情况分析算法运行时间
一般情况:情况复杂,分析难度大
渐近分析: 忽略T(n)的系数与低阶项,仅关注高阶项,用记号O表示
O记号(渐进上界)示例
Ω记号(渐进下界)
问题:如何比较不同算法的性能?
分析算法的运行时间
归纳基本操作 如:运算、赋值、比较
统一机器性能 假设基本操作代价均为1
统一机器性能后,算法运行时间依赖于问题输入规模与实例
最好情况:不常出现,不具有普遍性
最坏情况:确定上界,更具一般性 常用最坏情况分析算法运行时间
一般情况:情况复杂,分析难度大
渐近分析: 忽略T(n)的系数与低阶项,仅关注高阶项,用记号O表示