Suchen Sie zum Beispiel, wie man die Komplexität von O (n log n) berechnet?

Question

Ich bin neu in Data Structures und habe versucht, die Konzepte zu verstehen. Ich verstehe Big-O-Notation, und die Suche nach Beispielen bezieht sich auf O (n log n). Ich habe das Internet durchsucht, aber ich habe kein zufrieden stellendes Beispiel oder eine Implementierung - wo ich die Komplexität von O (n log n) sehen kann. Kann mich jemand auf ein besseres Beispiel und eine bessere Implementierung hinweisen?

Vielen Dank im Voraus

Answer 1

Es gibt einen wohlbekannten Satz in der Komplexitätstheorie, der Hauptsatz genannt wird. Sein Fall sagt, dass, wenn die Komplexität T(n) einen Algorithmus erfüllt die Gleichung

T(n) = a T(n/a) + b*n   (1) 

dann

T(n) = O (n log n)    (2) 

Die Gleichung (1) oben, als ob der Algorithmus funktioniert interpretiert werden kann, indem das Problem in a Aufspalten Teile und wendet sich für jeden Teil separat und dann etwas Arbeit an der vollständigen Eingabe. Dieses algorithmische Muster wird manchmal Merge and Recombine genannt.

betrachte das folgende Beispiel in Python

def f(x): 
    if len(x) > 1: 
     x1 = [z for z in x[1:] if z <= x[0]] 
     x2 = [z for z in x[1:] if z > x[0]] 
     return f(x1) + [x[0]] + f(x2) 
    else: 
     return x 

Diese Funktion implementiert einen rekursiven Algorithmus, der die Eingabeliste in zwei Teile aufspaltet und wendet sich unabhängig zu jedem Teil, die Ergebnisse dann verkettet. Wenn wir Glück haben und x und y Teile die gleiche Länge haben, dann kann die Komplexität des Algorithmus mit der Formel (2) oben mit a = 2 berechnet werden.

Wenn Sie mit der Sortierung und der Python-Sprache vertraut sind, würden Sie hier einen Algorithmus erkennen, der Quicksort emuliert, jedoch ohne die Komplexität der Sortierung in Place. Ein etwas saubereres Beispiel ist Merge sort, das in der Antwort von Christos erwähnt wird.

Answer 2

Ein klassisches Beispiel eines O(nlogn) Algorithmus ist dies von Merge Sort. Here würden Sie eine detaillierte Berechnung der Komplexität finden. Im Allgemeinen gibt es viele divide and conquer Algorithmen, die diese Komplexität haben.

Answer 3

Ich würde vorschlagen, die Cormen Einführung in die Algorithmen Page-151 (Heapsort) und 170 (Quicksort). Diese werden in diesem Buch ausführlich erläutert. Die Schlüsselidee in jedem Fall ist, dass Sie die grundlegende Operation, die durchgeführt wird, verstehen, die der Vergleich ist (in diesen beiden Fällen), und dann analysieren, indem Sie das Merkmal des Algorithmus selbst verwenden. Für Quicksort die Pivottalanalyse und für Heapsort den Heap-Anteil.

Dieses Buch enthält alles, was Sie wissen müssen, um die Komplexität zu analysieren.