美文网首页
Polynomial time 多项式时间

Polynomial time 多项式时间

作者: devilisdevil | 来源:发表于2021-04-30 08:28 被阅读0次

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^kck都是某个正整数: T(n) \leq cn^k (n \geq M)

举例

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

Refs 参考

相关文章

网友评论

      本文标题:Polynomial time 多项式时间

      本文链接:https://www.haomeiwen.com/subject/xmzgrltx.html