問題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の複雑さの上限を持つことを意味します。

シータ（n^2）は、問題を解決するために使用されるアルゴリズムの複雑さを表現する方法でもありますが、O（n^2）とは対照的にシータ（n^2）は、複雑さの下限と上限がnであることを意味します。 ^2。

また、アルゴリズムの下限の複雑さを示すO（Little-OH）である別の測定値もあります。

o（n^2）と同様に、アルゴリズムもo（n^3）およびo（n！）も意味するため、シータはより正確です。

Answer 2

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