c - 当我们为 50n logn 计算 Big-Oh 时，它是 O(n log n)？我们可以把 O(n^5) 当作 Big-Oh 吗？

Question

我最近遇到了一些渐近符号，当这个问题出现时，它是 50 n logn 并且根据流行的规则获得 Big-OH​​ 符号是简单地删除常数和低阶项。但是 50n logn 也是n^5 的 BIG-OH。 那么为什么 Big-oh 表示法更适合考虑 O(nlogn) 而不是 O(n^5)。 .

当在 wolfram 中将输入大小更改为 0 到 50 时，结果图如下

Answer 1

50.n.log(n) = O(n^5) 完全正确。这在数学上没有问题。我们可以找到一个常量 C = 1，这样对于所有 n 都高于某个值 10 我们有

|50.n.log(n)| < C.|n^5|

有关 formal definition 的信息，请参见维基百科

这是毫无疑问的。

如果我们更愿意说 50.n.log(n) = O(n.log(n)) 是因为我们经常想知道什么是增长最慢的函数 决定了算法的复杂性。这通常用于比较算法复杂度。