Что из следующего является наиболее точной классификацией проблемы x?

Question

Что из следующего является наиболее точной классификацией проблемы x?

• X находится в NP
• X находится в p
• X находится в O (n²)
• X находится в θ (n²).

Я бы очень признателен, если бы кто -нибудь мог объяснить мне ответ?

Я считаю, что это либо NP, либо P, но я действительно не уверен

Answer 1

NP или P означает, можно ли решить его во время полинома в не детерминированной машине (NP) или в детерминированной машине (P). Это отражает сложность проблемы, но не сложность алгоритма, который решает проблему.

В то время как o (n^2) означает, что алгоритм, анализируемый для решения проблемы, имеет верхнюю границу сложности n^2, когда n является входом.

Тета (n^2) также является способом выражения сложности алгоритма, используемого для решения проблемы, но тета (n^2) в отличие от O (n^2) означает, что нижняя и верхняя граница сложности N равен N ^2.

Есть также другая мера, которая представляет собой O (Little-OH), которая указывает на более низкую связанную сложность алгоритма.

Тета более точна, потому что, как o (n^2), означает только верхнюю границу, алгоритм также является O (n^3) и O (n!).

Answer 2

Θ(не²) ⊂ o (не²) ⊂ p ⊆ np