O(n) 和 O(1 + n) 之间的实际区别？

Question

O(n) 不是对 O(1 + n) 的改进吗？

这是我对差异的看法：

在）：

for i=0 to n do ; print i ;

O(1 + n)：

a = 1;
for i=0 to n do ; print i+a ;

...这只会减少到 O(n) 对吗？

如果目标时间复杂度是 O(1 + n)，但我有一个 O(n) 的解决方案，这是否意味着我做错了什么？

谢谢。

Answer 1

O(1+n) 和 O(n) 在数学上是相同的，因为您可以从形式定义或使用标准规则直接证明O( a(n) + b(n) ) 等于 O( a(n)) 和 O(b(n))。

在实践中，当然，如果你做 n+1 件事，它会（通常，依赖于编译器优化/等）比你只做 n 件事需要更长的时间。但是大 O 符号是谈论这些差异的错误工具，因为它明确地抛弃了这样的差异。