algorithm - 比较指数函数的增长率？

Question

假设我们有两个函数 f(n) = 2 ^{2 ⁿ⁺¹}和 g(n)=2 ^{2 ⁿ}。我想使用两种不同的方法来比较这两个函数的增长率。

方法一：取比

让我们定义 t(n) = f(n) / g(n)。然后

t(n) = f(n) / g(n)

= 2 ^{2 ⁿ⁺¹} / 2 ^{2 ⁿ}

= 2 ^{2 ^{n + 1} - 2 ⁿ}

= 2 ^{2 ⁿ}

所以我们假设 f(n) 比 g(n) 增长得快得多。

如前所述，令 t(n) = f(n) / g(n)。现在，让我们取两边的日志库：

lg t(n) = lg (f(n) / g(n))

= lg (2 ^{2 ⁿ⁺¹} / 2 ^{2 ⁿ} )

= lg 2 ^{2 ⁿ⁺¹} - lg 2 ^{2 ⁿ} )

= 2 ⁿ⁺¹ - 2 ⁿ

现在，让我们取两边的日志库：

lg lg t(n) = (n + 1) lg 2 / n lg 2

= (n + 1) / n

忽略常数项，我们得到 lg lg t(n) = 1，这是一个常数，因此 f(n) 和 g(n) 应该具有相同的增长率。

为什么我使用方法二得到错误的答案？

score 2 · Accepted Answer

我认为您的错误假设如下：

如果 log log f(x) / log log g(x) 是一个常数，则 f(x) = Θ(g(x))。

这是一个简单的反例。令 f(x) = x ²且 g(x) = x。然后

log log f(x) = log log x ² = log (2 log x) = log 2 + log log x

和

对数对数 g(x) =对数对数 x

这里，log log f(x) 和 log log g(x) 仅相差一个常数（即 log 2），但显然 f(x) 和 g(x) 以相同的速率增长是不正确的。换句话说，在记录两个函数的增长率后忽略常数是不安全的。

你的逻辑有第二个错误。如果你计算 f(n) / g(n)，你会得到

2 ^{2 ^{n + 1}} / 2 ^{2 ⁿ}

= 2 ^{2 ⁿ⁺¹ - 2 ⁿ}

= 2 ^{2 ⁿ}

如果你两次记录这个，你会得到

lg lg 2 ^{2 ⁿ}

= lg 2 ⁿ

= n

因此，比率的 log log 是 (n + 1) / n 甚至是不正确的；相反，它是 n，它仍然趋向于无穷大。这也会告诉你 f(n) 比 g(n) 增长得更快。

希望这可以帮助！

score 2 · Accepted Answer

2

你哪里出错了：“忽略常数项”。

t(n) = (n+1)/n = n/n + 1/n = 1 + 1/n > 1

于 2013-09-05T18:02:07.727 回答