我在基本的运行时理解方面遇到了一些麻烦，也许有人可以为我澄清一下。我将如何确定这个函数的运行时间？
我需要确定相当f = O(g)或f = omega(g)或f = theta(g)
f(n) = 100n + logn
g(n) = n + (logn) 2
所以100n和n顺序相同；并且在这一点上是线性time > log time;的，我还需要查看日志部分吗？或者我可以确定f = theta(g)吗？
问问题
762 次
1 回答
1
您可以安全地确定它们的数量级相同。无需查看“日志部分”。
这是针对这种特定情况的形式证明，一般证明可以从极限算术中得到证明。
让我们看看h(n) = f(n)/g(n)当 n 接近无穷大时的函数，如果它保持在 0 以上和m我们知道的某个数字以下f(x) = Theta(g(x))（因为 Theta 是如何定义的）。
所以我们有h(n) = (100n + logn)/(n + logn^2)
我们知道，如果我们为任何实数 x 证明这一点，它也适用于自然数。因此，足以证明：
h(x) = (100x + logx)/(x + logx^2)
我们通过 l'Hospital 的规则知道，如果分母和分母的导数存在并且收敛，则原函数的极限存在并且也等于相同的数。让我们应用它并得到：
lim x-> infinity , h(x) = (100x + logx)/(x + logx^2) =
lim x-> infinity , (100+1/x) / (1 + (2log(x) / x) )
我们知道当 x 接近无穷大时 1/x 接近 0，当 x 接近无穷大时 (2logx)/x 接近 0（用你的话来说（时间 > 对数时间））。所以我们从极限算术中得到
lim x-> 无穷大 h(x) = 100/1 = 100
由于极限存在于 R 中并且是非零的，我们得到 f(x) = Theta(g(x)) 这就是我们想要展示的。
于 2013-05-18T16:20:42.430 回答