
_START_ARTICLE_
伪多项式时间
_START_SECTION_
例子
_START_PARAGRAPH_
在素性测试中，使用较小的整数逐个对被测试数进行试除的算法被认为是一个伪多项式时间算法。对于给定的整数N，使用从最小的素数2开始，到为止的整数依次对N进行试除，如果均无法整除N，则N是素数，这个过程需要进行至多约次整数除法，即其时间复杂度为，为N的多项式。令D为N的二进制表示的位数，那么N可以表示为以2为底D的幂，因此素性测试问题的时间复杂度用D表示应为。因此，上述算法是一个伪多项式时间算法。_NEWLINE_其它被证明只具有伪多项式时间算法解的问题有背包问题，子集合加总问题。