函数 f(n) 的复杂度是多少 n=f(n).log(f(n))

Question

函数f(n)的复杂度是多少，最好是Big-O记法，f(n)满足条件n = f(n).log(f(n)) ,f(n) > 1 .假设登录 base 2.

我试图将 f(n) 从条件中分离出来，但无法完成。使用excel得到函数f(n)的图形后。似乎 f(n) = O(n^2) 但我不知道如何把它弄出来？

Answer 1

评论越来越长，所以这里有一个证明草图给你。这可能是家庭作业，所以请确保你学到了一些东西，而不是仅仅抄下来。

为了证明 f 是 O(n)，您必须证明存在 M 和 n1，其中 f(n) < M|n|对于所有 n > n1。

我们知道n = f(n) log(f(n))，所以M |n| = M |f(n)| |日志（f（n））|。

所以我们要寻找的是

的 M 和 n1

  f(n) < M |n| = M |f(n)| |log(f(n))|

对于 n > n1。

n、f 和 log f 都是正数，所以我们可以去掉 |.|得到

  f(n) < M f(n) log(f(n)) = M |n|

我们的目标是找到一个 M 和 n1

  f(n) < M f(n) log(f(n)) = M |n|

对所有 n > n1 都成立。选择 M = 1, n1 = 10, 然后

  f(n) < f(n) log(f(10)) <= f(n) log(f(n)) = |n|  (where M is now set to 1)

对于 n > n1。 f(n) log(f(10)) <= f(n) log(f(n)) 为真，因为 log(f(n)) 对于 n>n1 是单调的（家庭作业：证明这是真的） . f(n) < f(n) log(f(10)) 是平凡的，因为 log(f(10)) > 1.

这表明 f(n) 是 O(n)。

Answer 2

我认为复杂度甚至低于 O(n) - 即 O(n/ln(n))。半证明：

（用 n/ln(n) 代替 f(n)）

RHS = n/ln(n) * ln(n/ln(n)) = n/ln(n) * (ln(n) -ln(ln(n))) = = n - n * ln(ln(n))/ln(n) = n * (1-ln(ln(n))/ln(n)) = n*Theta(1) = Theta(n) = LHS

为清楚起见，我几乎在所有地方都跳过了 Theta 表示法。

What is the complexity of function f(n) with n=f(n).log(f(n))