算法解释的线性复杂度

Question

所以我在我的书中看到了这段话:

算法 arrayMax，用于计算 n 个整数数组中的最大元素，运行时间为 O(n)。

理由：算法数组执行的原始操作数- 每次迭代中的最大值是一个常数。因此，由于每个原始操作都在 常数时间，我们可以说算法 arrayMax 在输入上的 运行 时间 大小 n 最多是 n 的常数，也就是说，我们可以得出结论 运行 算法arrayMax的时间是O(n).

我不明白的部分是“..算法 arrayMax 在大小为 n 的输入上的 运行 时间最多是常数倍 n...”

“常数乘以 n”是什么意思？

Answer 1

在此上下文中，常数表示它是一个有限的可理解整数，一个整数。

出于 'a constant times n' 的目的，这意味着操作的每次迭代可能是 5、10、15 等操作，n 是应用程序将执行此操作的次数，因此, O(常数*n)

执行任务所需的操作数不变，但程序的规模最多可以有 n 个对象。