Randomize()

[life]

Doch es der Vergleich ist bei camper O(1).

@volkard: Dann probier doch mal Nexus Algorithmus aus. Der hat ja O(n) für die Gesamtlaufzeit ;).
Für den ursprünglichen Algorithmus müsste man die erwartete Laufzeit ausrechnen... Würd man spontan auf O(n^3 log(n)) tippen..

[volkard]

DeepCopy schrieb:

vokhard schrieb:

Also den Vergleich kriegten wir von O(n^2) über O(n) runter auf O(1).

Also ich weiß ja nicht wo du Informatik/Mathematik studiert hast aber es ist wirklich nicht O(1), mein letzter Kommentar dazu.

In diesem Sinne
Gruß Deep Copy

Der VERGLEICH, Du Nase! Du Weihnachtsmann!
Der Aufruf von checkme(i) war vorher quadratisch und jetzt ist er ersetzt durch das konstante check[x[i]].
Der Vergleich steckt noch in einer äußeren Schleife, weswegen der gesamte Algo O(viel) hat und nicht O(1), das ist klar.

[DeepCopy]

volkhard schrieb:

Der VERGLEICH, Du Nase! Du Weihnachtsmann!

Ich kann mir ein Grinsen nicht verkneifen, ich ein Weihnachtsmann

Nicht böse sein, aber woher sollte ich wissen das du mit VERGLEICH eine Stelle im Code und nicht den ganzen Algo meinst.

[camper]

DeepCopy schrieb:

... woher sollte ich wissen das du mit VERGLEICH eine Stelle im Code und nicht den ganzen Algo meinst.

Weil du damit angefangen hast, dich auf den Code, der den Vergleich durchführt, zu beschränken.

DeepCopy schrieb:

Lässt sich optimieren, auf reduzierte Komplexität von O(n²) zu O(n).

Alter Code:

...