本章会让你熟悉在全书中使用的算法设计和分析框架。虽然本章是独立的,但是仍包含一些对第3章、第4章使用的材料的引用。
在第1章里,以使用插入排序来解决排序问题开头。本章以定义伪代码开始,并使用伪代码来描述插入排序算法。之后,我们讨论插入排序是否能正确地排序,并分析它的运行时间。进行算法的运行时间分析,需要引入一种记号,该记号重点关注运行时间随着待排序的数增长的变化趋势。接着,我们介绍一种算法设计策略:分而治之,并使用分而治之策略来设计一种新的排序算法:归并排序。最后,我们分析了归并排序的运行时间。
网友评论