¿Cuál de las siguientes es la clasificación más precisa de un problema X?

Question

¿Cuál de las siguientes es la clasificación más precisa de un problema X?

• X está en NP
• X está en P
• X es en O (n ² )
• X está en T (n ² ).

Le agradecería si alguien podría explicar la respuesta de esto a mí?

Creo que es ya sea NP o P, pero realmente no estoy seguro

Answer 1

medios

NP o P si se puede resolver en tiempo polinómico en una máquina no determinista (NP) o en una máquina determinista (P). Esto refleja la complejidad del problema, pero no la complejidad de un algoritmo que resuelve el problema.

Mientras O (n ^ 2) significa que el ser algoritmo analiza para resolver un problema ha un límite superior de n ^ 2 complejidad cuando N es la entrada.

Theta (n ^ 2) es también una manera de expresar la complejidad de un algoritmo utilizado para resolver un problema, pero Theta (n ^ 2), en contraste de O (n ^ 2) significa que que el límite inferior y superior de complejidad es n ^ 2.

También hay otra medida que es O (poco-oh) que indica la complejidad límite inferior de un algoritmo.

Theta es más preciso porque como O (n ^ 2) medios justo en el límite superior, el algoritmo es también O (n ^ 3) y O (n!).

Answer 2

T ( n ² ) ? O ( n ² ) ? P ? NP