用大 O 表示法比较 2 个函数

Question

问题是 ：

\n\n

假设 f, g: N \xe2\x86\x92 N 是满足 f(n)=O(logn) 且 g(n) = \xce\xa9(nlogn) 的函数。\n是否有可能 f(n) = \xce\xa9(g(n))?

\n\n

我认为这是不可能的，因为 nlogn > logn，不确定它是否正确，也不知道如何证明它。

\n\n

提前致谢 ！

\n

Answer 1

不，这是不可能的。

\n\n

让我们假设这是可能的：

\n\n

\n
• g(n) = \xce\xa9(nlogn)==> 对于a足够g(n) > anlogn大的n.
\n
• f(n) = \xce\xa9(g(n))==> 对于b足够f(n) > bg(n) > banlogn大的n.
\n
• 让c = ab==>f(n) > cnlogn足够大n==> f(n) = \xce\xa9(nlogn)。
\n
• f(n) = O(logn)==> 对于d足够f(n) < dlogn大的n.
\n
• ==> cnlogn < f(n) < dlogn==> cnlogn < dlogn==> n < d/c。这是不可能的，因为n存在大于 的自然数d/c。==> 与最初的假设相矛盾。
\n

\n