Polynomial time 多项式时间

2021-04-30 本文已影响0人 devilisdevil

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 参考

wiki: Polynomial time

Polynomial time 多项式时间

举例

Refs 参考

猜你喜欢

热点阅读