“多项式级时间问题”是什么意思

Question

如题所述

Answer 1

多项式时间是相对于指数时间的，设问题的规模为N，则如果算法的时间复杂度为T(N)=aN^k1 + bN^k2 + cN^k3+....+xN^kx+... 其中k1>k2>k3...且是确定的常数，同时a,b,c...也都为常数，即T（N）是N的多项式，此时称该问题(算法)为具有多项式级时间。
与之相对的是指数级时间，即T(N)=ax^N，其中a为常数，x也为常数，称其为指数级时间。