Polynomial time 多项式时间

An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, that is, T(n) = O(n^k) for some positive constant k

如果一个算法复杂度小于某个多项式，那么这个算法就是多项式时间算法
或者说，当n大于某个M后，T(n)小于等于cn^k，c和k都是某个正整数： T(n) \leq cn^k (n \geq M)

举例

  • 二分查找复杂度log(n) \leq n，所以它是多项式时间算法
  • 快速排序平均复杂度nlog(n)，最坏复杂度n^2 （有什么算法平均时间复杂度是多项式的而最坏复杂度不是多项式的吗？如果没有那一般看平均时间复杂度就行？）

Refs 参考

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 多项式时间和伪多项式时间
    参考自：维基百科 伪多项式时间 在计算机理论领域中，若一个数值算法的时间复杂度可以表示为输入数值 的多项式，则称...
    曾悦_3b69阅读 2,005评论 0赞 0
  • 时间复杂度与空间复杂度
    算法（algorithm）本质上是一连串的计算。同一个问题可以使用不同算法解决，但计算过程中消耗的时间和资源可能千...
    pro648阅读 1,417评论 0赞 0
  • 算法(12)- NP完全性
    P L是{0, 1}* 的子集, 如果对任意的输入串x, 算法都能在多项式时间内判定(decide)x是否属于L,...
    陈码工阅读 3,276评论 0赞 2
  • 算法基础
    谨以此文，感谢我在这个学校最喜欢的两个老师之一——肖my老师。本文基本为老师上课说讲授内容加上一部分自己的感悟拼凑...
    A黄橙橙阅读 2,877评论 5赞 4
  • 2019－11－28 周四 阴
    今天感恩节哎，感谢一直在我身边的亲朋好友。感恩相遇！感恩不离不弃。 中午开了第一次的党会，身份的转变要...
    迷月闪星情阅读 10,620评论 0赞 11