2
条回答
写回答
写回答
-
-
在算法分析中，通常只需要分析时间复杂度的渐进行为，即分析出运行时间的渐进确界。
于是，渐进大于可以这样理解：设g(n)渐进大于f(n)
则存在数c>0和n0，使得对于任意 n >= n0 有 c*g(n) >= f(n).
多项式大于定义如下：
存在常数c>0,c1>0,c2>0，使得
c1 * f(n) * n ^ c <= g(n) <= c2*f(n)*n^c
它是一种更强的渐进大于。
譬如说：
n多项式大于n^(log 4 3)
取 c = 1 - log 4 3即可满足多项式大于定义。
但是nlogn仅仅渐进大于n
因为对于任意c>0,均有logn < n^c(由洛必达法则可知)。
主方法的第三种情况要求是多项式大于，故T(n) = 2 * T(n/2) + nlgn不能应用主方法2019-07-17 22:51:46赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
问答排行榜
最热
最新
推荐问答
