-2

次のうち、問題 X の最も正確な分類はどれですか?

  • XはNPにある
  • X は P にある
  • X は O(n 2 )にあります
  • X は Θ(n 2 ) にあります。

誰かが私にこれの答えを説明していただければ幸いです。

NPかPのどちらかだと思いますが、よくわかりません

4

2 に答える 2

2

NP または P は、非決定論的機械 (NP) または決定論的機械 (P) で多項式時間で解けるかどうかを意味します。これは問題の複雑さを反映していますが、問題を解決するアルゴリズムの複雑さは反映していません。

O(n^2) は、問題を解決するために分析されるアルゴリズムが、n が入力の場合に n^2 の複雑さの上限があることを意味します。

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

アルゴリズムの下限の複雑さを示す o(little-oh) という別の尺度もあります。

O(n^2) が上限を意味するように、アルゴリズムも O(n^3) および O(n!) であるため、シータはより正確です。

于 2011-01-11T23:32:09.797 に答える
1

Θ( n 2 ) ⊂ O( n 2 ) ⊂ P ⊆ NP

于 2011-01-11T23:34:57.420 に答える