Quale dei seguenti è il più precisa classificazione di un problema X?

Question

Quale dei seguenti è la classificazione più precisa di un problema X?

• X è in NP
• X è in P
• X è in O (n ² )
• X è in T (n ² ).

Le sarei molto grato se qualcuno potrebbe spiegare la risposta di questo a me?

Credo che sia uno NP o P, ma io non sono davvero sicuro

Answer 1

NP o P indica se può essere risolto in tempo polinomiale in una macchina non deterministica (NP) o in una macchina deterministica (P). Ciò riflette la complessità del problema, ma non la complessità di un algoritmo che risolve il problema.

Mentre O (n ^ 2) significa che l'essere analizzato algoritmo per risolvere un problema è un limite superiore di n ^ 2 complessità quando n è l'ingresso.

Theta (n ^ 2) è anche un modo per esprimere la complessità di un algoritmo utilizzato per risolvere un problema, ma Theta (n ^ 2) in contrasto di O (n 2 ^) significa che il limite inferiore e superiore di la complessità è n ^ 2.

C'è anche un'altra misura che è O (piccolo-oh) che indica la complessità limite inferiore di un algoritmo.

Theta è più precisa perché, come O (n ^ 2) significa proprio limite superiore, l'algoritmo è anche O (n ^ 3) e O (n!).

Answer 2

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