时间戳

首页 > 解决方案 > 我们是根据计算模型进行算法分析，还是根据“常识”进行分析？

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

问题描述

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

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

我的意思是，在《算法导论》和《算法设计手册》中，提到了一种叫做 RAM 计算模型的东西。在这些书中，据说在该模型下我们计算步数，但在其他书中没有提到这样的计算模型。

其他书籍讨论了算法行进路径的计数步骤，即以常识方式或以逻辑方式。所以，如果你们能帮助我解决这些问题，我将不胜感激：

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

标签： algorithmcomplexity-theoryanalysis

解决方案

我们的常识基于一个可以是隐式或显式的计算模型。通常在介绍性课程中，它是隐含的。明确地，您使用的通常是 RAM 模型。这是基于顺序处理的思想，每个简单的操作都需要固定的时间。所以你只计算步数。

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

当然，现实是完全不同的。正如https://gist.github.com/jboner/2841832所示，操作花费的时间完全不同。通过切换到使用排序而不是哈希查找，我个人看到工作从 5 天缩短到 1 小时。是的，哈希查找是O(1)，但是当数据由磁盘支持时，它的常量很可怕。分布式计算使事物并行运行。GPU 上的计算为您提供了大量的并行性……只要所有计算都以完美的步调运行。我们正在尝试构建量子计算机，理论上它可以给我们带来很多很多数量级的并行性......以失去像“if”这样的不可逆操作为代价。

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

推荐阅读