证明lg(n!)= O(n!)

用户名

由于某种原因,我很难找到一种证明这一点的好方法。总的来说,我对解决极限和数学感到非常生疏。

首先:我的印象是您可以根据乘法法来分隔限制。所以,目前我正要

LIM Ñ→∞(LG(n)的⋅n 0.5)⋅LIM ñ→∞((E / N)Ñ

与某事物的极限乘以0的极限相同。因此,它必须为0。

这是即使有效,或者我应该回去,只是学习得到n个0.5 ⋅lg(n)和其他类似化合物的功能呢?

显然,这个问题是微不足道的,我只是想知道我是否正在采取有效的方法。

古斯塔夫·拉尔森(Gustav Larsson)

这很容易证明。请记住,f(z) = O(z)如果存在M和z0,那么对于所有z > z0|f(z)| < M|z|

现在,由于我们微不足道地知道这|log(z)| < |z|一切z > 1,所以我们只能替代z = n!,这就是我们的证明。要明确,z0 = 1M = 1会做到这一点。

如果有人说这是不正确的,那么他们可能会忘记最常用的Big Oh符号(大写字母Omicron)提供了上限,因此界限不必太紧。

更新:关于极限乘数法则的注释。如果两个限制都存在,则只能打破这样的限制例如,如果当n接近无穷大时具有n / n的限制,则不能将其与n / 1 / n的限制相分离,因为n的限制不存在。您的第一个限制显然有所不同,因此您不能使用此方法。

本文收集自互联网,转载请注明来源。

如有侵权,请联系[email protected] 删除。

编辑于
0

我来说两句

0条评论
登录后参与评论

相关文章

来自分类Dev

证明或非证明Ω(n)=ω(n)UΘ(n)

来自分类Dev

证明n = o(2 ^ {f(n)})?

来自分类Dev

证明 g(n) 是 O(g(n))

来自分类Dev

复杂度理论中的O(lg(n))* O(lg(n))

来自分类Dev

如何证明以下函数hg(n)= O(f(n))

来自分类Dev

证明自然(n)为零

来自分类Dev

证明g(n)为o(f(n)),则f(n)+ g(n)为Theta(f(n))

来自分类Dev

证明 5nˆ2 + 2n - 1 对于 n >= 1 是 O(nˆ2)

来自分类Dev

证明O(n ^ 2)优于或劣于O(n ^ 2 log n)

来自分类Dev

证明∑ i至n(logi)的总和为O(nlogn)

来自分类Dev

证明存在10次交换的O(n)算法

来自分类Dev

证明f(n)=Θ(g(n))且g(n)=Θ(f(n))

来自分类Dev

对于任何底数a或b的证明O(loga n)= O(logb n)

来自分类Dev

如果f(n)= O(h(n)),则对于所有c> 0,c * f(n)= O(h(n))-证明挑战吗?

来自分类Dev

渐近符号:如何证明n ^ 2 =Ω(nlogn)?

来自分类Dev

n长度的直接证明序列

来自分类Dev

给定O(n lg n)中的协调文件列表,如何删除$ HOME中的特定符号链接?

来自分类Dev

为什么我的合并排序不像O(n * lg n))?

来自分类Dev

如何在Coq中证明(n = n)=(m = m)?

来自分类Dev

我无法用Idris证明(n-0)= n

来自分类Dev

Coq:证明n和(S n)的乘积是偶数

来自分类Dev

如果n = 100的O(lg(n))算法运行1秒,那么如何计算n = 1000需要多长时间?

来自分类Dev

如何证明从最小节点在BST中找到n-1次后继者是O(n)?

来自分类Dev

O(n)+ O(n)= O(n)?

来自分类Dev

证明h(n)> f1(n)-f2(n)> 0且f1(n)=Ω(g(n)和f2(n)= O(g(n)))则h(n)=Ω (g(n)

来自分类Dev

证明1 ^ k + 2 ^ k + .. + n ^ k的大欧米茄

来自分类Dev

证明L = {a ^ nb ^ m | n> = m}是不规则语言

来自分类Dev

如何使用求和符号证明算法为Θ(log n)?

来自分类Dev

在lg(n!)时间中运行的算法的时间复杂度

Related 相关文章

  1. 1

    证明或非证明Ω(n)=ω(n)UΘ(n)

  2. 2

    证明n = o(2 ^ {f(n)})?

  3. 3

    证明 g(n) 是 O(g(n))

  4. 4

    复杂度理论中的O(lg(n))* O(lg(n))

  5. 5

    如何证明以下函数hg(n)= O(f(n))

  6. 6

    证明自然(n)为零

  7. 7

    证明g(n)为o(f(n)),则f(n)+ g(n)为Theta(f(n))

  8. 8

    证明 5nˆ2 + 2n - 1 对于 n >= 1 是 O(nˆ2)

  9. 9

    证明O(n ^ 2)优于或劣于O(n ^ 2 log n)

  10. 10

    证明∑ i至n(logi)的总和为O(nlogn)

  11. 11

    证明存在10次交换的O(n)算法

  12. 12

    证明f(n)=Θ(g(n))且g(n)=Θ(f(n))

  13. 13

    对于任何底数a或b的证明O(loga n)= O(logb n)

  14. 14

    如果f(n)= O(h(n)),则对于所有c> 0,c * f(n)= O(h(n))-证明挑战吗?

  15. 15

    渐近符号:如何证明n ^ 2 =Ω(nlogn)?

  16. 16

    n长度的直接证明序列

  17. 17

    给定O(n lg n)中的协调文件列表,如何删除$ HOME中的特定符号链接?

  18. 18

    为什么我的合并排序不像O(n * lg n))?

  19. 19

    如何在Coq中证明(n = n)=(m = m)?

  20. 20

    我无法用Idris证明(n-0)= n

  21. 21

    Coq:证明n和(S n)的乘积是偶数

  22. 22

    如果n = 100的O(lg(n))算法运行1秒,那么如何计算n = 1000需要多长时间?

  23. 23

    如何证明从最小节点在BST中找到n-1次后继者是O(n)?

  24. 24

    O(n)+ O(n)= O(n)?

  25. 25

    证明h(n)> f1(n)-f2(n)> 0且f1(n)=Ω(g(n)和f2(n)= O(g(n)))则h(n)=Ω (g(n)

  26. 26

    证明1 ^ k + 2 ^ k + .. + n ^ k的大欧米茄

  27. 27

    证明L = {a ^ nb ^ m | n> = m}是不规则语言

  28. 28

    如何使用求和符号证明算法为Θ(log n)?

  29. 29

    在lg(n!)时间中运行的算法的时间复杂度

热门标签

归档