算法时间复杂度及P、NP、NP-Complete、NP-Hard问题

算法的时间复杂度

如果某个算法的复杂度可以表示为$O(n^k)$，即问题规模n出现在底数的位置，这种复杂度称为多项式时间复杂度；

如果某个算法的复杂度表示为$O(k^n)$或$O(n!)$，这种复杂度称为指数型时间复杂度。

相同问题规模下（同时这个问题规模不是太小），指数型时间复杂度远远大于多项式时间复杂度。