다음 중 문제 X의 가장 정확한 분류는 무엇입니까?

Question

다음 중 문제 X의 가장 정확한 분류는 무엇입니까?

• X는
• X는
• X가 O 인 P에 NP이다 (N 2⁾
• Θ는 X (n은 2^)이다.

누구든지이 답변을 설명해 주시면 감사하겠습니다.

가 나는 NP 또는 P 중 하나입니다 생각하지만, 난 정말 모르겠어요

Answer 1

NP 또는 P는 비 결정적 기계 (NP) 또는 결정적 기계에서 다항식 시간에 해결 될 수 있는지 여부를 의미한다 (P). 이는 문제의 복잡성을 반영하지만 문제를 해결하는 알고리즘의 복잡성은 반영하지 않습니다.

O (n^2)는 문제를 해결하기 위해 분석되는 알고리즘이 n을 입력으로 할 때 n^2 복잡도의 상한을 가짐을 의미합니다. 012 (0^2)는 문제 해결에 사용 된 알고리즘의 복잡성을 표현하는 방법이기도하지만 O (n^2)와는 대조적으로 Theta (n^2)는 상한 및 하한 복잡도는 n^2입니다.

또한 알고리즘의 하위 복잡성을 나타내는 o (little-oh)라는 또 다른 측정 값이 있습니다.

Theta는 O (n^2)와 마찬가지로 상한을 의미하므로 O (n^3) 및 O (n!)이기 때문에 더 정확합니다. 이 과제는

Answer 2

Θ ( N²) ⊂ O ( N²) ⊂ P ⊆ NP