以下哪项是对问题 X 的最准确分类？
- X 在 NP
- X 在 P 中
- X 在 O(n 2 )
- X 在 Θ(n 2 ) 中。
如果有人能向我解释这个问题的答案，我将不胜感激？
我相信它是NP或P，但我真的不确定
问问题
643 次
2 回答
2
NP或P表示它是否可以在非确定性机器（NP）或确定性机器（P）中以多项式时间求解。这反映了问题的复杂性，而不是解决问题的算法的复杂性。
而 O(n^2) 意味着当 n 是输入时，被分析解决问题的算法具有 n^2 复杂度的上限。
Theta(n^2) 也是表达用于解决问题的算法复杂度的一种方式，但 Theta(n^2) 与 O(n^2) 相比意味着复杂度的下限和上限为 n ^2。
还有另一个度量是 o(little-oh)，它表示算法的下限复杂度。
Theta 更精确，因为就像 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 回答