我们是根据计算模型进行算法分析，还是基于“常识”进行分析？

Question

最近，我读了这些关于算法的书，特别是关于算法分析的部分：

• 算法介绍。第三版。TCRC
• 算法设计手册第二版。斯基纳
• 算法设计J.Kleinberg & Eva Tardos
• 算法。第四版。塞奇威克
• 算法。S. Dasgupta，C. Papadimitriou & Vazirani
• 其他几本书

在那之后，我有点困惑，因为我不完全理解算法计数步骤的起源。

我的意思是，在“算法和算法设计手册”的介绍中，我们提到了所谓的RAM计算模型。在这些书中，据说在这个模型下我们计算步骤，而在其他书中没有提到这样的计算模型。

另一本书讨论了算法运行的路径的计数步骤，也就是说，以一种常识的方式或逻辑的方式。所以，如果你们能帮我回答这些问题，我会很感激的：

步骤计数方法(其他书籍)与使用计算模型(TCRC和S.Skiena)之间的关系(或区别)是什么？当有人谈到计算步骤来分析算法时，我可以假设他指的是使用计算模型(RAM)吗？

Answer 1

我们的常识是建立在计算模型的基础上的，它可以是隐含的，也可以是显式的。通常在入门课程中，它是隐式的。显式地使用的通常是RAM模型。它基于顺序处理的思想，其中每个简单的操作都需要恒定的时间。所以你只需数台阶。

您可以在http://people.seas.harvard.edu/~cs125/fall14/lec6.pdf找到该模型的正式描述。

当然，现实是完全不同的。正如https://gist.github.com/jboner/2841832所显示的那样，操作所花费的时间相差很大。我个人已经看到工作从5天变成了1小时，转而使用了一种类型而不是哈希查找。是的，哈希查找是O(1)，但是当数据被磁盘支持时，哈希查找有一个可怕的常量。分布式计算具有并行操作的功能。GPU上的计算为您提供了大量的parallelism..as，只要所有计算都在完美的锁步中运行。我们正在努力制造量子计算机，理论上它可以给我们更多数量级的parallelism..at，失去像"if“这样的不可逆转的运算的成本。

我们可以创建处理所有这些复杂性的模型。但是，在您了解基本知识之前，没有必要考虑其中的任何一项。这是RAM模型中标准的“计数操作”。