Ich habe die Zeitkomplexität der Blasensortierung im besten Fall nach dem in Buch ALGORITHMEN 2.2 verwendeten Mothod abgeleitet. Aber die Antwort erwies sich als O (n ^ 2).
Hier ist meine Ableitung, hoffe, dass mir jemand helfen kann, herauszufinden, wo es falsch ist:
%Vor%}
%Vor%T (n) = c1 + c2n + c3 (n - 1) + c4 (n - 1) + c5t5 + c6t6 + c7t7 + c8t8 = c1 + c2n + c3 (n - 1) + c4 (n - 1) + c5 [t1 (i = 0) + t1 (i = 1) + ... + t1 (i = n - 2)] + c6 [t2 (i = 0) + t2 (i = 1) + ... + t2 (i = n-2)] + c7 [t3 (i = 0) + t3 (i = 1) + ... + t3 (i = n-2)] + c8 [t4 (i = 0) + t4 (i = 1) + ... + t4 (i = n-2)];
in seiner besten Besetzung, ist die Reihenfolge bereits vor dem Sortieren positiv. Dann sollte t8 0 sein.
T (n) = c1 + c2n + c3 (n - 1) + c4 (n - 1) + c5 [t1 (i = 0) + t1 (i = 1) + ... + t1 (i = n-2)] + c6 [t2 (i = 0) + t2 (i = 1) + ... + t2 (i = n-2)] + c7 [t3 (i = 0) + t3 (i = 1 ) + ... + t3 (i = n-2)]
Die Zeitkomplexität ist O (n ^ 2)
Ihre Implementierung
%Vor%fehlt die Kontrolle darüber, ob in der inneren Schleife ein Austausch stattgefunden hat und ob die äußere Schleife aufgebrochen wurde, falls dies nicht der Fall war.
Dieses Steuerelement macht es möglich, dass der beste Fall (ein bereits sortiertes Array) O (n) ist, da dann bei der ersten Ausführung keine Swaps in der inneren Schleife vorhanden sind.
%Vor%Ich bin mir nicht sicher, was du zählst. Wenn Sie über Vergleichsortieralgorithmen sprechen, sollten Sie im Allgemeinen die Anzahl der durchgeführten Vergleiche zählen. Blasensortierung wird als solche angesehen. In diesem Fall ist der von Ihnen vorgestellte Algorithmus O (n ^ 2).
Wenn Sie die Anzahl der Swaps zählen, kann sein O (1) oder vielleicht sogar einer O (0) sagen. Es ist jedoch selten, Bubble sort so zu analysieren.
Sie können Bubble jedoch sehr einfach verbessern, um O (N) im besten Fall zu erhalten. ZB durch Einführen eines Flags swap_was_made . Wenn es am Ende von inner for falsch ist, kannst du es beenden. Im besten Fall wird die Komplexität auf O (N) reduziert (eine innere Schleife). Im Falle einer gerechten, gleichmäßigen Verteilung reduziert es die erwartete oder durchschnittliche Komplexität auf O (N ^ 2/2) ... Aber bitte überprüfen Sie mich darauf, dass ich falsch liegen könnte. Hat die Mathematik hier nicht gemacht.
Tags und Links time-complexity bubble-sort