“多項式級時間問題”是什麽意思

多項式時間是相對於指數時間的，設問題的規模為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也為常數，稱其為指數級時間。