Sortierung eines Array überprüfen

Zitat von that

O(1) schaffst du nur, wenn du die gültigen Eingabewerte auf Array beschränkst, die in den ersten 3 Elementen garantiert unsortiert sind.

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ür

Zitat von watchout

Das is zwar nicht deutsch der Satz

"s" <- bitte an der richtigen Stelle einsetzen.

Zitat von watchout

aber ich denke du meinst dass ich hätte schreiben sollen dass bei unsortiert die Laufzeit Ω(1) und O(n) ist - Sorry dafür

Sieht richtiger aus - was das Ω ist musste ich jetzt selbst nachschauen

Zitat von watchout

(Wo du ein s einfügen willst is mir nicht klar )

Zwischen "Array" und " ". Wenns dir dann noch immer nicht deutsch vorkommt, klick auf den ersten Link in meiner Sig.

Zitat von watchout

Ich sitz gerade an ner AlgoDat-Übung - bin also sozusagen vorgeschädigt (wirkt ungefähr wie )

Übertreibs nicht, das könnte dauerhafte Schädigungen hervorrufen.

Könnte bitte jemand erklären was

Code:

Ω() und O()

ist, damit ich (und sicher viele andere auch) den Thread wieder verstehen?

Edit I:
-> http://en.wikipedia.org/wiki/Big_O_notation

Edit II:
Warnung
Der obige Link kann Ihnen und den Menschen in Ihrer Umgebung erheblichen Schaden zufügen

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));

Schon hat man aus linearem Zeitverhalten ein quadratisches gemacht. Bei kleinen Datenmengen ist das noch egal, aber je größer die Anzahl der Elemente wird, desto schlimmer wirkt sich n² aus.

du kannst es so verstehen dass O(n²) eine Menge aller Funktionen darstellt die n² als Obere Schranke haben

verdammt...das muss ich am wochende auch wieder alles wiederholen, hab am montag entwurf und analyse von algorithmen teilklausur. rekursive zeitgleichungen ahoi