algorithm - 确定算法中的步骤数

Question

我正在查看我的 Data Structures and Algorithms注释，并遇到了以下有关时间复杂度和大 O 表示法的示例: 左侧的列计算每行中执行的操作数。我不明白为什么第一个例子中的几乎所有行前面都有 2 的倍数，而其他两个例子却没有。显然这不会影响生成的 O(n)，但我仍然想知道 2 是从哪里形成的。

Answer 1

对此我只能找到一个解释:幻灯片作者的草率。

在正确的分析中，必须解释在什么时间针对什么输入执行了什么样的操作(例如第 21 页的 this book)。如果没有这个，您甚至无法确定我们将 2 个数字相乘算作 1 次运算还是 2 次运算还是其他运算？

这些幻灯片不一致。例如:

在幻灯片 1 中，currentMax = A[0] 需要 2 次操作。如果您将查找数组中的第 0 个元素作为 1 个操作并将其分配为另一个操作，则有点有意义。但是在幻灯片 3 中，s = s + X[i] 的 n 迭代需要 n 次操作。这意味着 s = s + X[i] 需要 1 次操作。我们只增加一个计数器也是有道理的。

但是完全不一致，因为a = X[0]是2次运算，而a = a + X[0]<没有意义 你做更多的地方只需要 1.