大 O(n(n+k)) = O(n^2 + nk)？

Question

写 O(n(n+k)) 和写 O(n² + nk) 一样吗？ 此外，像 O(n(n+k)logn) 这样添加 logn 如何影响复杂性？

我目前正在学习大 o 表示法，并对时间复杂度的这个小细节感到困惑。

Answer 1

1. 如果 K 是一个常数，那么你可以抛出它，意味着忽略它，因为如果 n 变得很大，你将看不到导致 k 的差异，所以 O(n(n+K)) 等于 O(n * n)，是的。 2. 在这个 O(n(n+k)logn) 中，当你忽略 K 时，它就变成了 O(n * n *logn)

Answer 2

是的，这是纯粹的数学概念（参见https://en.wikipedia.org/wiki/Big_O_notation）。因此，所有有效的数学运算都是允许的。

这意味着您可以轻松扩展数学表达式中的括号（就像您所做的那样）。