Lequel des éléments suivants est la plus précise la classification d'un problème X?

Question

Lequel des éléments suivants est la plus précise la classification d'un problème X?

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

Je serais très heureux si quelqu'un pourrait expliquer la réponse de ce à moi?

Je crois qu'il est soit NP ou P, mais je ne suis vraiment pas sûr

Answer 1

P moyens NP ou si elle peut être résolu en temps polynomial dans une machine non déterministe (NP) ou dans une machine déterministe (P). Cela reflète la complexité du problème, mais pas la complexité d'un algorithme qui permet de résoudre le problème.

Alors que O (n ^ 2) des moyens que l'être analysé algorithme pour résoudre un problème a une limite supérieure de n ^ 2 complexité lorsque n est l'entrée.

Theta (n ^ 2) est également une manière d'exprimer la complexité d'un algorithme utilisé pour résoudre un problème mais Theta (n ^ 2) en opposition de O (n ^ 2) signifie que ce que la partie inférieure et la limite supérieure de la complexité est n ^ 2.

Il y a aussi une autre mesure qui est o (petit-oh) qui indique la complexité limite inférieure d'un algorithme.

Theta est plus précis parce que, comme O (n ^ 2) des moyens que la limite supérieure, l'algorithme est O (n ^ 3) et O (n!).

Answer 2

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