big-o - 两次通过数组 O(n) 或 O(2n)

Question

我在面试蛋糕上练习了一些问题，并在问题 2给出的解决方案使用两个单独的 for 循环(非嵌套)，解决方案提供者声称他/她在 O(n) 时间内解决了它。据我了解，这将是 O(2n) 时间。是我想错了吗，还是解决方案提供商搞错了？

采访蛋糕节选:

Answer 1

Big-O 表示法提示您算法执行时间如何取决于输入数据。当您看到时间复杂度为 O(n) 时，您就会明白输入和执行时间之间存在 线性 依赖关系。没有提到常量。

根据定义 Ο(g(n)) 是一个函数集，对于其中的每一个，以下语句成立:存在这样的正常数 c 和 n₀ 0 ≤ f(n) ≤ cg(n) 适用于所有 n ≥ n₀。如果您的 g(n) 本身有一个不会有任何区别的常量，您会看到定义使用的是任意常量 c。

最终我们得到:O(cg(n)) = O(g(n))。在您的特定情况下 O(cn) = O(2n) = O(n)。它们都代表同一组函数。