big-o - 如何证明大o关系

Question

嘿，标题可能有点过头了，因此，如果您知道如何改善标题，请更正它。

作为一项家庭作业，我得到了以下几项作业:

令f(n)和g(n)为渐近正函数。证明或否定以下每个猜想。

a. f(n) = O(g(n)) implies g(n) = O(f(n))

现在，我真正的问题是-您将如何以正式方式证明这一点？我知道上面的内容很容易，因为我可以轻松地提供一个反例来反驳它，但是出于争论的缘故，让我们说我们想在没有反例的情况下执行此操作，因为当然，在其他一些示例中，这种情况仍会继续这是行不通的。

我有点卡住，我写下了以下不等式(<=小于或等于)

f(n) <= c1 * g(n)
g(n) <= c2 * f(n)

但是我不确定如何将这两个不等式组合成一个(不等式)方程并进行反证。我敢肯定，这是一件很容易被我忽略的事情，而且我现在很愚蠢-但是任何有关如何做到这一点的指针/具体例子都将是很棒的，因此我应该能够这些问题的其余部分由我自己解决。

Answer 1

您为什么要在不使用反例的情况下反驳它？这是反驳索​​赔的最直接方法。

如果必须证明这一点，那么您当然不能使用反例。在这种情况下，相反的方法可以很好地工作-假设该声明是错误的，然后说明如何导致逻辑上的不一致。

在这种情况下，您从f(n) <= c1 * g(n)为true开始，因为这就是f(n) = O(g(n))的含义。现在，您要假设g(n) <= c2 * f(n)对所有f和g都是正确的(最后一部分非常重要，因为您可以选择f和g如此正确)，并说明为什么它不起作用。对您的提示是:选择一个f和g使其不起作用，并通过选择c1和c2来表明它不起作用。