algorithm - 如果 g , h 是 f(n) = O(g(n)) 和 g(n) = O(h(n)) 证明 f(n) = O(h(n)) 的函数

Question

我目前正在上我的第一门离散数学课，但遇到了一些麻烦。这是我第一次遇到 big Oh，我在理解这个特殊问题时遇到了一些麻烦。

我了解证明 n <= O(n)因为我可以在数学上证明存在这样一个常数，它适用于 n >= k

的所有值

如果f , g , h是这样的函数 f(n) = O(g(n))和 g(n) = O(h(n))

使用类里面给出的大哦的定义来证明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))

更好？

Answer 1

使用 Big 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 .