为了比较两个函数的渐近阶,当n变为无穷大时,我计算了第二个函数的第一个函数的极限.
答案是2(我必须使用l'hopital的规则),这意味着对于非常高的n值,log(n ^ 2)大于log(5n)
我的问题是:说log(n ^ 2)渐近地大于log(5n)是不正确的？
我的朋友告诉我,当第一个函数的限制超过第二个函数是常数时,这意味着它们的渐近顺序是相等的.有人可以证实吗？
实际上log(5n)= log 5 + log n,log(n ^ 2)= 2 log n,因此log(n ^ 2)大于log 5.此外,我们可以说它渐近地大于log 5n.渐近是一种定义:
渐近的术语意味着任意接近一个值或曲线(即,采取某种限制).对给定曲线C渐近的直线或曲线A称为C的渐近线.
并且取决于你的情况,但在算法中,我们不考虑常数因子,通常我们说它们是相同的顺序,实际上我们的限制不依赖于常数因子,我们说它们是相同的log (5n) = log 5 + log n或Θ或Ω .在算法的概念中,它们是渐近相等的函数.
更新更清楚:在算法中我们说A(n)渐近地大于B(n) if
lim n→∞A(n)/ B(n)=∞
在你的情况下,极限值是2(或1/2),所以它们渐近相等.