Beispiele für Algorithmen mit O (1) -, O (n log n) - und O (log n) -Komplexitäten

114

Welche Algorithmen verwenden wir täglich mit O (1) -, O (n log n) - und O (log n) -Komplexitäten?

Rachel
quelle
6
Warum Wiki? Es ist weder eine Umfrage noch subjektiv. Sie möchte konkrete Beispiele für die Big-O-Eigenschaften.
Paxdiablo
4
Wiki, weil es keine einzige richtige Antwort hat, hat es mehrere Antworten.
Jason S
2
Wikipedia hat auch eine gute Liste. en.wikipedia.org/wiki/Time_complexity
Homer6

Antworten:

234

Wenn Sie Beispiele für Algorithmen / Gruppen von Anweisungen mit zeitlicher Komplexität wünschen, wie in der Frage angegeben, finden Sie hier eine kleine Liste -

O(1) Zeit

  • Zugriff auf den Array-Index (int a = ARR [5];)
  • Einfügen eines Knotens in die verknüpfte Liste
  • Pushing und Poping on Stack
  • Einfügen und Entfernen aus der Warteschlange
  • Ermitteln des übergeordneten oder linken / rechten untergeordneten Elements eines Knotens in einem in Array gespeicherten Baum
  • Zum nächsten / vorherigen Element in der doppelt verknüpften Liste springen

O(n) Zeit

Kurz gesagt, alle Brute-Force-Algorithmen oder Noob-Algorithmen, die Linearität erfordern, basieren auf der Komplexität der O (n) -Zeit

  • Durchlaufen eines Arrays
  • Durchlaufen einer verknüpften Liste
  • Lineare Suche
  • Löschen eines bestimmten Elements in einer verknüpften Liste (nicht sortiert)
  • Zwei Zeichenfolgen vergleichen
  • Nach Palindrom suchen
  • Counting / Bucket Sort und auch hier finden Sie eine Million solcher Beispiele ....

O(log n) Zeit

  • Binäre Suche
  • Finden der größten / kleinsten Zahl in einem binären Suchbaum
  • Bestimmte Divide and Conquer-Algorithmen basieren auf linearen Funktionen
  • Berechnung der Fibonacci-Zahlen - beste Methode Die Grundvoraussetzung besteht darin, NICHT die vollständigen Daten zu verwenden und die Problemgröße bei jeder Iteration zu verringern

O(n log n) Zeit

Der Faktor 'log n' wird eingeführt, indem Divide and Conquer berücksichtigt wird. Einige dieser Algorithmen sind die am besten optimierten und werden häufig verwendet.

  • Zusammenführen, sortieren
  • Heap Sort
  • Schnelle Sorte
  • Bestimmte Divide and Conquer-Algorithmen basieren auf der Optimierung von O (n ^ 2) -Algorithmen

O(n^2) Zeit

Diese sollen die weniger effizienten Algorithmen sein, wenn ihre O (nlogn) Gegenstücke vorhanden sind. Die allgemeine Anwendung kann hier Brute Force sein.

  • Blasensortierung
  • Sortieren durch Einfügen
  • Auswahl Sortieren
  • Durchqueren eines einfachen 2D-Arrays
Karan Bajaj
quelle
5
Was ist mit n!? Ich habe mich gefragt, welcher gängige Algorithmus n verwendet!?
Y_Y
Zugriff auf einen HashMap-Wert sowie auf komplexere Algorithmen wie eine LRU-Implementierung, die O (1) mithilfe einer HashMap und einer doppelt verknüpften Liste erreicht, oder Implementierung eines Stapels mit PUSH / POP / MIN-Funktionalität. Auch die rekursive Implementierung von Fibonacci fällt unter N!.
ländlicher Kodierer
10
Meine OCD möchte, dass Sie O(log n)die O(n)Liste so ändern, dass sie vor der Liste steht, damit die Liste vom Besten zum Schlechtesten geordnet ist. haha :)
Sam Eaton
4
Das Durchlaufen eines 2D-Arrays ist tatsächlich O (nxm), es sei denn, es handelt sich um eine quadratische Matrix.
Simon Peck
1
Das Problem des "reisenden Verkäufers" ist ein Beispiel für n! (n Fakultät) auch
Ju66ernaut
28

Ein einfaches Beispiel dafür O(1)könnte sein return 23;: Unabhängig von der Eingabe wird dies in einer festen, endlichen Zeit zurückgegeben.

Ein typisches Beispiel O(N log N)wäre das Sortieren eines Eingabearrays mit einem guten Algorithmus (z. B. Mergesort).

Ein typisches Beispiel, wenn O(log N) wäre das Nachschlagen eines Werts in einem sortierten Eingabearray nach Halbierung.

Alex Martelli
quelle
28

O (1) - Die meisten Kochvorgänge sind O (1), das heißt, es dauert eine konstante Zeit, auch wenn mehr Personen zum Kochen da sind (bis zu einem gewissen Grad, weil Ihnen in Ihrem Topf / Ihren Pfannen möglicherweise der Platz ausgeht und müssen das Kochen aufteilen)

O (logn) - etwas in Ihrem Telefonbuch finden. Denken Sie an die binäre Suche.

O (n) - Lesen eines Buches, wobei n die Anzahl der Seiten ist. Es ist die Mindestzeit, die zum Lesen eines Buches benötigt wird.

O (nlogn) - Ich kann nicht sofort an etwas denken, das man jeden Tag tun könnte, das nlogn ist ... es sei denn, Sie sortieren Karten durch Zusammenführen oder schnelles Sortieren!

Chii
quelle
2
Das Kochen eines Bratens dauert viel länger als das Braten eines Mini-Bratens :-)
paxdiablo
4
Normalerweise dauert es jedoch genauso lange, bis zwei Mini-Braten gegen einen Mini-Braten gekocht sind, vorausgesetzt, Ihr Ofen ist groß genug, um hinein zu passen!
Chii
1
Sehr aufschlussreich! Ich nehme an, die Aufgabe, ein Telefon oder Adressbuch aus einer Liste von Namen / Nummern zusammenzustellen, könnte O (n log n) sein
squashed.bugaboo
10

Ich kann Ihnen einige allgemeine Algorithmen anbieten ...

  • O (1): Zugriff auf ein Element in einem Array (dh int i = a [9])
  • O (n log n): schnell oder zusammengeführt (im Durchschnitt)
  • O (log n): Binäre Suche

Dies wären die Bauchreaktionen, da dies nach einer Art Hausaufgaben- / Interviewfrage klingt. Wenn Sie nach etwas Konkreterem suchen, ist es etwas schwieriger, da die Öffentlichkeit im Allgemeinen keine Ahnung von der zugrunde liegenden Implementierung (natürlich Sparing Open Source) einer beliebten Anwendung hat und das Konzept im Allgemeinen auch nicht für eine "Anwendung" gilt.

Scannerschraube
quelle
4

O (1): Finden Sie den besten nächsten Zug im Schach (oder gehen Sie für diese Angelegenheit). Da die Anzahl der Spielzustände endlich ist, ist es nur O (1) :-)

Carsten
quelle
5
Ja, normalerweise können Sie Zeit gegen Platz eintauschen. Ich habe dies tatsächlich für ein Tic-Tac-Toe-Spiel getan, da es nur 3 ^ 9 Zustände gibt (weniger, wenn Sie Rotationen intelligent handhaben). Schach hat jedoch eine etwas größere Anzahl von Staaten :-)
paxdiablo
1
Das Problem ist, dass ich nur O(1)Nanosekunden leben werde , und Sie wissen sicherlich, welche O(1)zuerst auftreten werden ...
Zardav
3

Die Komplexität der Softwareanwendung wird nicht gemessen und nicht in Big-O-Notation geschrieben. Es ist nur nützlich, die Komplexität von Algorithmen zu messen und Algorithmen in derselben Domäne zu vergleichen. Wenn wir O (n) sagen, meinen wir höchstwahrscheinlich "O (n) Vergleiche " oder "O (n) arithmetische Operationen". Das heißt, Sie können kein Paar von Algorithmen oder Anwendungen vergleichen.

P Shved
quelle
1
Das stimmt nicht wirklich. Wenn ein Algorithmus eine O (N) -Zeitkomplexität aufweist, bedeutet dies, dass seine Laufzeit für eine Konstante k durch k * N Schritte begrenzt ist. Es ist nicht wirklich wichtig, ob "Schritte" CPU-Zyklen, Montageanweisungen oder (einfache) C-Operationen sind. Diese Details werden durch die Konstante k verborgen.
Igor ostrovsky
Ganz zu schweigen davon, dass in vielen praktischen Fällen das "c" eines O (logN) -Algorithmus es schlechter macht als ein einfacherer O (N) -Algorithmus.
Zed
Haha, ja, und mit N meinen wir dann die Länge der Eingabe auf einem Turing-Maschinenband - wodurch die Implementierung der vertikalen Form der Teilung exponentiell dauert. :-) Jede Domain hat ihre eigenen Anforderungen und ihren eigenen Abstraktionsbereich.
P Shved
3

O (1) - Löschen eines Elements aus einer doppelt verknüpften Liste. z.B

typedef struct _node {
    struct _node *next;
    struct _node *prev;
    int data;
} node;


void delete(node **head, node *to_delete)
{
    .
    .
    .
}
Sigjuice
quelle
2

Sie können Ihrer Liste folgende Algorithmen hinzufügen:

O(1)- Feststellen, ob eine Zahl gerade oder ungerade ist; Arbeiten mit HashMap

O(logN) - Berechnung von x ^ N,

O(N Log N) - Längste zunehmende Folge

Rachvela
quelle
1

O (n log n) ist bekanntlich die Obergrenze dafür, wie schnell Sie eine beliebige Menge sortieren können (unter der Annahme eines Standardmodells und eines nicht hochparallelen Rechenmodells).

Carsten
quelle
0

0 (logn) - Binäre Suche, Peak-Element in einem Array (es kann mehr als einen Peak geben) 0 (1) - In Python wird die Länge einer Liste oder eines Strings berechnet. Die len () -Funktion benötigt 0 (1) Zeit. Der Zugriff auf ein Element in einem Array dauert 0 (1) Mal. Der Push-Vorgang in einem Stapel dauert 0 (1). 0 (nlogn) - Sortierung zusammenführen. Das Sortieren in Python dauert nicht lange. Wenn Sie also listname.sort () verwenden, dauert es nicht lange.

Das Durchsuchen von Notizen in einer Hash-Tabelle dauert aufgrund von Kollisionen manchmal mehr als konstant.

Abhinav Vajpeyi
quelle
0

O (2 N )

O (2 N ) bezeichnet einen Algorithmus, dessen Wachstum sich mit jeder Addition zum Eingabedatensatz verdoppelt. Die Wachstumskurve einer O (2 N ) -Funktion ist exponentiell - sie beginnt sehr flach und steigt dann meteorisch an. Ein Beispiel für eine O (2 N ) -Funktion ist die rekursive Berechnung von Fibonacci-Zahlen:

int Fibonacci (int number)
{
if (number <= 1) return number;
return Fibonacci(number - 2) + Fibonacci(number - 1);
}

quelle
Tower of Hanoiwäre ein besseres Beispiel gewesen.
Ashish Duklan