算法设计手册解法错误？

Question

我从很多来源读到过大 O 表示法，包括 Skiena和 Wikipedia条目，Example其中的部分指出:

In typical usage, the formal definition of O notation is not used directly; rather, the O notation for a function f(x) is derived by the following simplification rules:

• If f(x) is a sum of several terms, the one with the largest growth rate is kept, and all others omitted.

• If f(x) is a product of several factors, any constants (terms in the product that do not depend on x) are omitted.

solution至 problem 2.2是 O((n^3)/3)。不应该省略“/3”，还是我遗漏了什么？

Answer 1

常数不需要省略，它们只是不携带任何信息——O(n^3) 与 O(n^3/3) 相同。您会注意到引用的段落讨论的是典型用法，而不是严格的要求。

查看具体答案，解渐近等价于 n^3/3。虽然在形式上与 O(n^3) 没有任何不同，但我猜这个想法是通过给出 O( n^3/3).