数据结构与算法----绪论

算法的性质

• 又穷性
• 能行性
• 确定性
• 终止性

- 输入输出

算法的描述

• 自然语言描述
• 自然语言加数学公式
• 编程语言描述

- 伪代码描述

常法设计模式

• 枚举法

  根据具体问题枚举出各种可能，从中选出有用信息或者问题的解。这种方法利用计算机的速度优势，在解决问题时十分有效。

• 贪心发

  根据问题的信息尽可能做出部分的解，并基于部分解逐步扩充得到完整的解。在解决复杂问题时，这种做法未必能得到最好的解。

• 分治法

  把复杂问题分解为相对简单的子问题，分别求解，最后通过组合起子问题的解的方式得到原问题的解。

• 回溯法（搜索法）

  专指通过探索的方式求解。如果问题很复杂，没有清晰的求解路径，可能就需要分步骤进行，而每一步骤又可能有多种选择。在这种情况下，只能采用试探的方式，根据实际情况选择一个可能方向，当后面的求解方向无法继续时，就需要退回前面的步骤，另外选择求解路径，这种动作成为回溯。

• 动态规划法

  在一些复杂情况下，问题求解很难直截了当地进行，因此需要在前面的步骤中积累信息，在后续步骤中根据已知信息，动态选择已知的最好求解路径（同时可能进一步积累信息）。

• 分支限界法

可以看作搜索方法的一种改良形式，如果在搜索过程中可以得到一些信息，确定某些可能的选择实际上并不真正有用，就可以及早将其删除，以缩小求解空间，加速问题求解过程。

运算时间计算

一般法则

法则1 - for循环

一个for循环的运行时间至多是该for循环内部那些语句的运行时间乘以迭代的次数。

法则2 - 嵌套的for循环

从里向外分析这些循环。在一组嵌套循环内部的一些语句总的运行时间为该语句的运行时间乘以该组所有的for循环的大小的乘积
例如，下列程序片断为O（

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！