Bubblesort

[Test100]

Hallo,

Bubblesort muss ja das Array welches ich sortieren möchte (n (n-1)) / 2 mal durchlaufen um alle Elemente zu sortieren.
Soweit ist mir das klar.

Was sagt aber O(n^2) aus?
In keinen meiner Versuche werden bei einem Array mit 5 Elementen 25 Operationen benötigt.
Zum anderen widerspricht die 2. Formel der 1.

 

[anti-held]

Das beschreibt die Komplexität des Algorithmus.
Bei der Komplexität werden Konstanten vernachlässigt.
Also werden das -1 und das /2 einfach weggelassen.

 

[Test100]

Warum werden bei der Komplexität Konstanten vernachlässigt.
Muss ich das einfach so als gegeben akzeptieren, oder gibts da eine Herleitung ?

 

[anti-held]

Das ist einfach so.
Bei der Berechnung werden:
1. Konstanten entfernt (wie die -1 und das /2)
2. nur der am schnellsten steigende Wert verwendet

Beispiel: 2n*5n + 3n + 0.1n*0.2n*0.3n
1. ohne Konstanten: n^2 + n + n^3
2. nur am schnellsten steigender Wert: n^3
-> O(n^3)

 

[Test100]

gelöscht

 

[anti-held]

Die Komplexität sagt nur aus wie "gut" ein Sortieralgorithmus ist.

 

[Test100]

Das heißt, das man damit garnichts berechnen kann, sondern dass hier nur grob wiedergegeben wird wie sich der Rechenaufwand entwickelt.

Ich persönlich sehe die Formel als nicht besonders sinvoll an.
Nicht mal die Steigung (1. Ableitung) stimmt von n^2 mit (n (n-1) /2) überein.

 

[JavaMeister]

O(n^2) ist eine Menge an Funktionen, die nicht wesentlich schneller Steigen als n^2.

Wenn man also n^2 + 1 hat, dann steigt diese nicht wesentlich mehr als n^2

Man kann also sagen, dass n^2 + 1 Teil von O(n^2) ist.

Siehe auch Landau-Symbole

 

[ceving]

Warum werden bei der Komplexität Konstanten vernachlässigt.
Muss ich das einfach so als gegeben akzeptieren, oder gibts da eine Herleitung ?

Definitionen kann man nicht herleiten.

 

[JavaMeister]

Definitionen kann man nicht herleiten.

Quatsch. Das ist keine Definition.

Das sind Mengen, die man sehr wohl herleiten kann. Gehört in den Bereich der Analysis.

 

[ceving]

Quatsch. Das ist keine Definition.

Ne? https://de.wikipedia.org/wiki/Landau-Symbole#Definition

Das sind Mengen, die man sehr wohl herleiten kann.

Mach mal.

 

[JavaMeister]

Du hast gerade den Absatz datz gequotet. Du lässt dich von dem Wort "Definition" zu der Aussage "das ist so" hinreisen, die hier einfach nicht sitmmt.

 

[s4ke]

O(n^2) ist eine Menge an Funktionen, die nicht wesentlich schneller Steigen als n^2.

Wenn man also n^2 + 1 hat, dann steigt diese nicht wesentlich mehr als n^2

Man kann also sagen, dass n^2 + 1 Teil von O(n^2) ist.

Siehe auch Landau-Symbole

Ich glaube, der Begriff obere Schranke triffts am besten und hilft glaube ich auch dem TE am Besten weiter, was das Verständnis angeht.

@TE:

Wenn ein Algorithmus in O(n^2) liegt bedeutet das, dass er in der Menge ALLER Algorithmen liegt, deren Ausführungszeit maximal von der Anzahl der Eingangswerte n quadratisch (also n^2) abhängt. Aus Einfachheitsgründen werden hier Konstanten (auch Vorfaktoren wie etwa z.B. in 3(n^2)) und Terme niedrigerer Ordnung weggelassen, da diese den Algorithmus nicht so sehr charakterisieren wie der einflussreichste Term (in dem Fall n^2).

Das ist also nur eine Art Algorithmen zu klassifizieren und keinesfalls eine exakte Beschreibung der Laufzeit, welche normalerweise nicht eine so große Wichtigkeit einnimmt..

 

[minzee]

Es kann sogar sein, dass sich O-Kalkül und Laufzeit genau andersrum verhalten. Dass in gewissen Fällen ein schlechteres O-Kalkül sogar schneller läuft.

 

[anti-held]

Zum Beispiel ist der Heapsort bei einer vorsortierten Liste viel langsamer als der Bubblesort, obwohl er eine besser Komplexität hat.

 

[arilou]

Das ist ein Denkfehler.
Für jeden Algorithmus gibt es verschiedene Komplexitätsangaben, i.A. zumindest für "worst case" und "average case", manchmal auch für "best case", sofern das einen Sinn hat.

Bubblesort hat im "best case" O(n); dies mit dem worst case eines anderen Algorithmus zu vergleichen, muss man dann a) deutlich machen und b) begründen, warum das sinnvoll ist.

 

[anti-held]

Es kann sogar sein, dass sich O-Kalkül und Laufzeit genau andersrum verhalten. Dass in gewissen Fällen ein schlechteres O-Kalkül sogar schneller läuft.

Ich habe nur ein Beispiel genannt.

 

[ceving]

Du hast gerade den Absatz datz gequotet. Du lässt dich von dem Wort "Definition" zu der Aussage "das ist so" hinreisen, die hier einfach nicht sitmmt.

Dann tu der Welt doch was gutes und berichtige den Wikipedia-Artikel.

 

[s4ke]

Dann tu der Welt doch was gutes und berichtige den Wikipedia-Artikel.

Wer hat dich denn dazu gebracht, so aggressiv zu reagieren? Die ursprüngliche Aussage, die ja anscheinend diesen Disput hier gestartet hatte war ja "Die Definition lässt sich nicht herleiten", stimmt übrigens in dem Kontext, dass eine Definition der Situation entsprechend gewählt (hergeleitet) werden kann. Der Fairness halber muss man aber zudem sagen, dass die Aussage "Quatsch das ist keine Definition" von JavaMeister auch nicht richtig war.

Solche Aussagen bringen nur unnötig Unfrieden und könnten doch auch etwas freundlicher ausgedrückt werden (wir sind hier in einem Forum, alle machen das hier nur freiwillig) und eine unnötige persönliche Schlacht bringt dem Threadersteller gar nichts.

 

[ceving]

Wer hat dich denn dazu gebracht, so aggressiv zu reagieren?

Wo siehst du Aggressionen?

Im Wikipedia-Artikel steht an vier Stellen, dass es sich um eine Definition handelt.



Es besteht hier eine gegenteilige Ansicht darüber. Eins von beidem kann nur richtig sein: entweder es ist eine Definition oder es ist keine Definition. Wenn der Wikipedia-Artikel falsch ist, ist es das naheliegendste von der Welt, den dort mehrfach gemachten Fehler richtig zu stellen. Ich würde sogar soweit gehen zu sagen, dass man als sozial verantwortlich agierendes Individuum die Pflicht hat, Fehler, die andere in der Wikipedia gemacht haben, zum Wohle der Allgemeinheit zu berichtigen.

 

[Moro]

Es kann sogar sein, dass sich O-Kalkül und Laufzeit genau andersrum verhalten. Dass in gewissen Fällen ein schlechteres O-Kalkül sogar schneller läuft.

Die Komplexität sagt nur aus wie "gut" ein Sortieralgorithmus ist.

Die Komplexität, speziell hier die O-Notation sagt aus, wie sich Algorithmen bei extrem großen Datenmengen im schlechtesten Fall Verhalten. Die Praxis zeigt, dass der schlechteste Fall häufiger auftritt als der beste Fall. Deshalb ist die O-Notation ein sinnvolles Kriterium da man so die Kosten einschätzen kann und man nicht Gefahr läuft, dass der Rechenaufwand nicht bewältigt werden kann. Der Heapsort ist vor allem für extrem große Datenmengen geeignet.

Wenn ihr beide worst- and best-Case Vergleiche über die Rechenzeit macht, dann schreibt das auch so. Die O-Notation hat mit euren "Laufzeitspielchen" jedenfalls nichts zu tun. Das O-Kalkül ist einfach nur die oberste Schranke, die ein Algorithmus annehmen kann - nicht mehr und nicht weniger.