您好，我想知道这个函数的 Big-Oh 是什么：f(n) = 7n – 3nlogn+100000。我检查了其他类似的问题。有人说因为 nlogn 是 -3 我们可以忽略它，因此结果是 O(n)。我咨询了我的教授，他说不，我们不会忽略负面因素，仍然选择其中最大的一个，因此 Big-Oh 将是 O(nlogn)。不忽略负面我最终得到了这个。我对吗？？
7n – 3nlogn+100000 ≤ (7+3+10000) nlogn where c= 100010 & n≥n0
7n – 3nlogn+100000 ≤ 100010 nlogn n0= 2
O(nlogn) – Linear logarithmic or linearithmic
还是更像
7n - 3nlogn + 100000 ≤ 100010 n where c= 100010 & n≥n0 & n0 = 1
非常感谢
如果你看一下big-O notation 的正式定义，你会注意到 f(x) = O(g(x)) 如果存在常数 c 和 x 0使得
∀x > x 0。|f(x)| ≤ c|g(x)|
请注意，这里有绝对值条。因此，虽然这是真的
7n - 3nlogn + 100000 ≤ 100010 n
在你提到的情况下，你真的需要证明
|7n - 3nlogn + 100000| ≤ 100010 |n|
这通常不是真的。利用你需要有绝对值柱的事实，你可以通过重复分析来证明这个函数是 Θ(n log n)，但要注意观察符号翻转。一种方法是使用三角不等式：
|7n - 3n 对数 n + 100000|
≤ |7n| + |-3n 对数 n| + |100000|
= 7|n| + 3|n 记录 n| + |100000|
≤ 7n + 3n log n + 100000
< 7n log n + 3n log n + 100000 n log n（例如当 n > 10 时）
= 100010 n 日志 n
所以函数是O(n log n)。您也可以重复此分析以获得匹配的下限。
希望这可以帮助！