1

您好，我想知道这个函数的 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

非常感谢

4

1 回答 1

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)。您也可以重复此分析以获得匹配的下限。

希望这可以帮助！

于 2013-06-16T15:24:45.060 回答