algorithm - 定义步数

Question

根据 this

Let n be a parameter that measures the size of the problem, and let R(n) be the amount of resources the process requires for a problem of size n. In our previous examples we took n to be the number for which a given function is to be computed, but there are other possibilities. For instance, if our goal is to compute an approximation to the square root of a number, we might take n to be the number of digits accuracy required. For matrix multiplication we might take n to be the number of rows in the matrices. In general there are a number of properties of the problem with respect to which it will be desirable to analyze a given process. Similarly, R(n) might measure the number of internal storage registers used, the number of elementary machine operations performed, and so on. In computers that do only a fixed number of operations at a time, the time required will be proportional to the number of elementary machine operations performed.

和

... For instance, if we count process steps as “machine operations” we are making the assumption that the number of machine operations needed to perform, say, a multiplication is independent of the size of the numbers to be multiplied, which is false if the numbers are sufficiently large. Similar remarks hold for the estimates of space. Like the design and description of a process, the analysis of a process can be carried out at various levels of abstraction.

我通常尝试通过计算单个操作执行了多少次并将所有操作加总来计算步骤数(例如 1 条 if 语句、n 次乘法、n 次加法 = 2n+1 = 2n = n 次操作，其中 n 是输入)。这本书使计算步数时似乎有不同的东西要计算。也就是说，要计算的步骤可能会有所不同。我的问题是:

• 在计算步数时，除了寄存器和基本的机器操作之外，还有其他可以计算的东西吗？
• 我相信我在确定增长顺序时计算了基本的机器操作。是否存在我们计算的步骤不应该是基 native 器操作(例如寄存器)的示例程序？
• 这句话令人困惑:“在一次只执行固定数量操作的计算机中，所需时间将与执行的基 native 器操作数量成正比。”这是否涵盖所有计算机？是否有计算机一次执行不同数量的操作？

Answer 1

这取决于你算什么。

您计算的内容定义了您在分析中使用的“模型”，例如RAM model .

使用 a 模型，您可以对程序的行为做出一些预测。这些预测是否有任何好处——我们可以通过在不同的问题规模下运行我们的实际程序来实际测量——告诉我们我们使用的执行模型是否有任何好处，它是否与实际发生的事情保持良好的对应在我们的计算机中，它是否是有用的。

分析经验 运行时行为可以通过在 log-log plot 上绘制运行时间与问题大小的关系图来完成.我们会得到一些曲线；任何曲线都可以用一系列直线来近似；对数图上的直线表示增长的幂规则:

t ~ n^a <==> log(t) ~ a log(n)。

Empirical orders of growth for the win!

比照。 this Q&A entry我在这个网站上。此外，Todd Lehman 的答案中的对数-对数图的很好的例子here .

---

更新:关于你的最后一个要点，并行计算机可能一次执行不同数量的操作，这取决于可用资源和/或计算的细节当前正在执行的任务阶段——就像引用的 Material 所说的那样，在过程的早期(比如)乘以一些数字，而它们仍然足够小，需要 O(1) 机器操作；当它们变大时就不是这样了。

此外，现代 CPU 可以(将？)同时执行多项操作，这取决于 pipeline 中当前指令的具体情况。 ^(*)(有些组合更适合这种情况，有些则不太适合)。

---

^(*) 维基百科说:“指令流水线是一种在单个处理器内实现指令级并行性的技术。”