以下哪项是问题x的最精确分类？

Question

以下哪项是问题x的最精确分类？

• X在NP中
• x在p中
• x在o中（n²)
• x在θ中（n²).

如果有人可以向我解释答案，我会非常感谢？

我相信是NP或P，但我真的不确定

Answer 1

NP或P表示它可以在非确定性机器（NP）还是确定性机器（P）中在多项式时间内解决。这反映了问题的复杂性，但不能反映解决问题的算法的复杂性。

而o（n^2）表示正在分析解决问题的算法在n是输入时具有n^2复杂性的上限。

theta（n^2）也是一种表达用于解决问题的算法的复杂性的方法^2。

还有另一种措施是O（Little-OH），它指示算法的下限复杂性。

theta更为精确，因为像O（n^2）一样，仅表示上限，算法也为O（n^3）和O（n！）。

Answer 2

Θ(n²）⊂o（n²）⊂p⊆np