截止现在,我们一直在关心算法的有效实现。我们看到:当给出一个算法时,并不需要说明所需要的数据结构,由程序员来选择合适的数据结构使得运行时间尽可能地短。
在这一章里,我们将注意力从算法的实现转向算法的设计。截止目前,我们看到的算法都很直接和简单。第9章里有些算法很特别,需要额外地讨论来展示它们的正确性。
在这一章里,我们将重点讨论5种常用来解决问题的算法类型。对于许多问题来说,有可能不止一种算法会奏效。具体来说,对每种类型的算法,我们都会
- 介绍通用的设计方法;
- 列举若干个实例;
- 尽可能地多讨论时间复杂度和空间复杂度;
网友评论