Что из следующего является наиболее точной классификацией проблемы x?
-
10-10-2019 - |
Вопрос
Что из следующего является наиболее точной классификацией проблемы x?
- X находится в NP
- X находится в p
- X находится в O (n2)
- X находится в θ (n2).
Я бы очень признателен, если бы кто -нибудь мог объяснить мне ответ?
Я считаю, что это либо NP, либо P, но я действительно не уверен
Решение
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!).
Другие советы
Θ(не2) ⊂ o (не2) ⊂ p ⊆ np