如果f(n) = O(g(n))，g(n) = O(h(n))，其中f、g、h是函数，请证明f(n) = O(h(n))。

Question

我目前正在学习离散数学，并遇到了一些困难。这是我第一次接触大O符号，我对这个特定问题有点困惑。

我理解证明 n <= O(n) 是因为我可以数学上证明存在这样的常数，对于所有值 n >= k 都成立。

如果 f，g，h 是函数，使得 f(n) = O(g(n)) 和 g(n) = O(h(n)) 使用课堂上给出的大O符号定义来证明 f(n) = O(h(n)) 我的答案是： |f(n)| <= U1|g(n)| for all n >= k |g(n)| <= U2|h(n)| for all n >= j 因此 |f(n)| <= U3|h(n)| for all n >= i 因此 f(x) = O(h(x)) 我试图在办公时间去见教授，但她说我的证明是错误的，但并没有说明原因。我已经花了很长时间，现在不知道该怎么办。任何帮助都将不胜感激...

好吧！让我再试一次！ |f(n)| <= U1|g(n)| for all n >= k |g(n)| <= U2|h(n)| for all n >= j 令 i 等于 k ∨ j 中最大的一个。

令 U3 等于 U1 * U2 f(n) <= U3|h(n)| for all n >= i 因此 f(n) = O(h(n)) 更好了吗？

- Razzek

---

你可能在Math StackExchange上会有更好的运气。 - Ayush

这不是数学，而是带有大O符号的基本算法。这是作业问题吗？ - thang

“U3”和“i”应该是什么？它们会从天上掉下来吗？ - Daniel Fischer

顺便提一下，这个属性被称为传递性。 - Aziz

在这里，你有一个很好的证明：http://www.brpreiss.com/books/opus4/html/page60.html - Erre Efe

Answer 1

使用大O符号定义：

f = O(g) iff exist c, n0 > 0 such that forall n >= n0 then 0 <= f(n) <= cg(n)

g = O(h) iff exist k, n1 > 0 such that forall n >= n1 then 0 <= g(n) <= kh(n)

现在我们来看最后一个不等式，并将所有成员除以c: 0 <= f(n)/c <= g(n)，我们可以在第二个不等式中代入g(n)： 0 <= f(n)/c <= kh(n)。最后将所有成员乘以c，就得到了0 <= f(n) <= kch(n)，这是f = O(h)的定义：

f = O(h) iff exist j, n2 > 0 such that forall n >= n2 then 0 <= f(n) <= jh(n)

在我们的情况下，它是这样的：n2 = max(n0, n1) 和 j = ck。

- Simon

---

为什么n2必须是n0和n1中的最大值？ - user2639830

Answer 2

你可以使用巴赫曼-兰道符号的限制解释。

然后，您可以使用以下推理：

- oxilumin

---

似乎他们没有使用限制来定义O。 - svick

商的极限通常不存在。f \in O(g) 意味着 lim sup |f(x)/g(x)| < \infty，因此如果您用 lim sup 替换您的极限，您将得到一些东西。 - Daniel Fischer

@DanielFischer 是的。一般来说，您是正确的，我们必须使用上确界极限而不是极限。 - oxilumin

Answer 3

如果您将第二个不等式代入第一个不等式，您应该得到U3 = U1 * U2，但是“i”是关键点。我认为（但我的理论日子已经过去了，所以我可能错了），您可以优雅地得出一个n >= argmax{ k, j }。

- Viç

Answer 4

使用另一种大O符号的定义：

抱歉显示有问题，我无法按照自己的意愿完成。

- Török Kristóf