Welche der folgenden ist die genaue Zuordnung eines Problems X?

Question

Welche der folgenden ist die genaue Zuordnung eines Problems X?

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

Ich wäre sehr dankbar, wenn jemand die Antwort von mir dies erklären könnte?

Ich glaube, es ist entweder NP oder P, aber ich bin wirklich nicht sicher

Answer 1

NP oder P Einrichtung, ob es in polynomialer Zeit in einer nicht deterministischen Maschine (NP) oder in einer deterministischen Maschine (P) gelöst werden kann. Dies spiegelt die Komplexität des Problems, aber nicht die Komplexität eines Algorithmus, der das Problem löst.

Während O (n ^ 2) bedeutet, daß die Algorithmus Wesen ein Problem hat eine obere von n ^ 2 Komplexität gebunden zu lösen, untersucht, wenn n die Eingabe.

Theta (n ^ 2) ist auch eine Möglichkeit, die Komplexität eines Algorithmus zur Expression verwendet, um ein Problem zu lösen, aber Theta (n ^ 2), im Gegensatz von O (n ^ 2), dass, dass die unteren und oberen Schranke Komplexität ist n ^ 2.

Es gibt auch eine andere Maßnahme, die o ist (wenig oh), die die untere Grenze der Komplexität eines Algorithmus zeigt.

Theta ist präziser, da, wie O (n ^ 2) bedeutet gerade obere Grenze der Algorithmus auch für O (n ^ 3) und O (n!).

Answer 2

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