算法设计基础-最重要的两个工具

两个基础

1. 算法设计中的一项重要的技术是缩小允许的实例的集合，直到找到正确有效的算法为止。

2. 要利用好已有的算法，您必须学会基本过程中的“抽象地”描述问题。根据定义好的结构和算法对应用程序进行建模是实现解决方案的最重要的一步。

RAM 和 大O

1. RAM计算模型

   将机器抽象为一个简单的机器，在这个机器上进行计算：

   • 每个简单的操作（+，*，-，=，if，call）只需一个时间步。
   • 循环和子例程不被视为简单操作
   • 每次内存访问仅需一个时间步长，而无需注意缓存或磁盘中的内容

2. 大O

   这些复杂性中的每一个都定义了一个数字函数，表示时间与问题大小的关系。但是时间上的复杂性是如此复杂，以至于我们必须简化它们以实现利用。为此，我们需要使用大O符号

   首先，要精确计算复杂度非常困难，因为它倾向于：

• 变化很大，不稳定

• 需要太多细节才能精确指定。因为计算最坏情况下执行的RAM指令的确切数量需要把整个计算机程序的细节考虑进来。

  大O符号会精确到不影响我们算法比较的详细程度。

  一个原则

• 最重要的原则：Big Oh符号和最坏情况分析是极大简化我们比较算法效率的功能的工具。

• 大O的通俗解法：找一个c，不管n怎么变大，$g(n)$都是其上界。注意，$g(n)$是比较大的那一个