Zitat von Neo-=IuE=-
ähm i mein wennst pech hast und das array nur gleiche werte hat und nur der letzte wert kleiner/größer is, dann hast O(2*n) 
URL: https://www.overclockers.at/coding-stuff/sortierung_eines_array_ueberpruefen_152234/page_2 - zur Vollversion wechseln!
Das is zwar nicht deutsch der Satz, aber ich denke du meinst dass ich hätte schreiben sollen dass bei unsortiert die Laufzeit Ω(1) und O(n) ist - Sorry dafürZitat von thatO(1) schaffst du nur, wenn du die gültigen Eingabewerte auf Array beschränkst, die in den ersten 3 Elementen garantiert unsortiert sind.
Zitat von Neo-=IuE=-ähm i mein wennst pech hast und das array nur gleiche werte hat und nur der letzte wert kleiner/größer is, dann hast O(2*n)
)Zitat von watchoutDas is zwar nicht deutsch der Satz
Zitat von watchoutaber ich denke du meinst dass ich hätte schreiben sollen dass bei unsortiert die Laufzeit Ω(1) und O(n) ist - Sorry dafür
der Satz is mit absicht genauso verbaut wie deiner obenZitat von that"s" <- bitte an der richtigen Stelle einsetzen.
(Wo du ein s einfügen willst is mir nicht klar )Ich sitz gerade an ner AlgoDat-Übung - bin also sozusagen vorgeschädigt (wirkt ungefähr wieZitat von thatSieht richtiger aus - was das Ω ist musste ich jetzt selbst nachschauen
)Zitat von watchout(Wo du ein s einfügen willst is mir nicht klar
Zitat von watchoutIch sitz gerade an ner AlgoDat-Übung - bin also sozusagen vorgeschädigt (wirkt ungefähr wie
omg, was ein kleines "s" so bewirken kann - jetzt macht der Satz richtig Sinn!Zitat von thatZwischen "Array" und " ". Wenns dir dann noch immer nicht deutsch vorkommt, klick auf den ersten Link in meiner Sig.
Könnte bitte jemand erklären was
ist, damit ich (und sicher viele andere auch) den Thread wieder verstehen?Code:Ω() und O()
Vorweg; Bei solchen Themen ist das deutsche Wikipedia imho besser (http://de.wikipedia.org/wiki/Landau-Symbole)
Grob gesagt, die O und Ω bzw. auch Θ geben an, wie lange ein Algorithmus läuft, dabei werden praktisch alle Konstanten und auch Teile eines Polynoms mit niederer Ordnung vernachlässigt.
Dabei gibt O(f(n)) die obere "Grenze", Ω(f(n)) die untere und Θ(f(n)) obere und untere Grenzen an
dh. hat eine Schleife (warum auch immer) 3n³+10n² Durchläufe, hat die Schleife in der Landau(Θ )-Notation eine Laufzeit von Θ(n³)
hat sie mindestens n und maximal n³ , dann hat sie Ω(n) und O(n³)
Wen das Ganze wirklich interessiert sollte sich nächstes Semester die Vorlesung "Algorithmen und Datenstrukturen 1" auf der Uni seiner Wahl geben - das Ganze ist doch etwas heftiger (Aber es is eine der interessanteren Vorlesungen)
Wen das Ganze nicht so wirklich interessiert, hier ist das Wichtige für die Praxis aus dem ganzen O(n) usw. Zeug zusammengefasst:
Man sollte sich ungefähr bewusst sein, welches Zeitverhalten eine Funktion in Relation zur Datenmenge hat. Das kann eben u.a. sein:
O(1) - konstant: Die Funktion braucht immer ca. die gleiche Zeit, unabhängig von der Datenmenge. Ob diese Zeit kurz oder lang ist, sagt das allerdings nicht aus. Aber für die doppelte Datenmenge braucht es die gleiche Zeit.
O(n) - linear: Doppelte Zeit für die doppelte Menge. Die klassische Schleife.
O(n²) - quadratisch: Vierfache Zeit für die doppelte Datenmenge, hundertfache Zeit für die zehnfache. Sowas entsteht, wenn man zwei Schleifen ineinander schachtelt (die beide über die selbe Größenordnung von Datenmenge gehen). Die primitiven Sortieralgorithmen haben z.B. quadratisches Zeitverhalten.
Der klassische Grund für unnötig langsame Programme sind gedankenlos verschachtelte Algorithmen mit O(n) oder schlechter.
Beispiel: Um in einer verketteten Liste das n-te Element zu finden, muss man vom Anfang an durchgehen und mitzählen, das ist also O(n). Angenommen man hat so eine Liste mit einer Methode getNthElement. Irgendwo anders verwendet man diese Liste wie folgt:
Code:for (int i = 0; i < myList.getNumberOfElements(); ++i) tuIrgendwasMit(myList.getNthElement(i));
Das konnte ich noch aus den Artikeln rauslesen. Wenn man aber etwas tiefer in die Materie geht und versucht http://en.wikipedia.org/wiki/Big_O_...rmal_definition bzw. http://de.wikipedia.org/wiki/Landau...male_Definition so zu verstehen, dass man da einen zusammenhang erkennt -> 
Zumindest gehts mir so
Und was das sein soll, versteh ich auch nicht so ganz:
Eine eine Funktion T(n) als Element einer Menge(?) O(n²)?
du kannst es so verstehen dass O(n²) eine Menge aller Funktionen darstellt die n² als Obere Schranke haben
Ah Das macht das Ganze ja richtig lesbar
verdammt...das muss ich am wochende auch wieder alles wiederholen, hab am montag entwurf und analyse von algorithmen teilklausur. rekursive zeitgleichungen ahoi
Omg wenn ich die entstehenden Schäden der Leute aus diesem Thread auf meine Kappe nehmen muss na servas. Da brauch ich eh nixmehr essen, weil die Gerichtskosten ziemlich hoch sein werden.
Klingt alles recht intressant, aber jetzt hab ich auch nichtmehr die Motivation mir das ganze nochmal genau durchzulesen. Wird morgen oder am Donnerstag abend gemacht.
overclockers.at v4.thecommunity
© all rights reserved by overclockers.at 2000-2025