5

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

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

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

用课堂上给出的big oh的定义来证明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))

更好的？

4

3 回答 3

3

使用大 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。

于 2013-01-20T17:38:09.530 回答
1

您可以使用 Bachmann-Landau 符号的极限解释。

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

推理

于 2013-01-20T17:34:51.297 回答
0

如果您将第二个不等式替换为第一个不等式，您最终应该得到U3 = U1 * U2，但是您所谓的“i”是关键点。我认为（但我的理论时代已经过去很久了，所以我可能错了）你可以优雅地结束n >= argmax{ k, j }.

于 2013-01-20T17:27:41.463 回答