camper schrieb:
SeppJ schrieb:
HarteWare schrieb:
SeppJ schrieb:
Kommt mir ungeheuer umständlich und eingeschränkt vor. Wieso nicht einfach durchiterieren und das Kriterium prüfen? Was hat dich geritten, da Rekursion einzubauen?
O(n) vs O(log(n)) Komplexität, wenn ich mich nicht irre. Soll zumindest in der Theorie die "divide and conquer" Methode sein.
Blödsinn. Die Werte sind doch nicht geordnet. Und wenn sie geordnet wären, bräuchtest du nicht suchen. Du stocherst hier bloß zufällig im Nebel rum, bis du etwas findest.
Wenn du sicher bist, sollte es nicht schwer fallen ein Beispiel zu konstruieren, bei dem der Algorithmus versagt?
Allgemein:
Unabhängige, zufällige Zahlen. Dann ist iteratives Durchgehen O(1) und HarteWares Vorgehen ist weiterhin O(log(n)). HarteWares Vorgehen ist dann gut, wenn die Zahlen "stetig" sind (ja, es sind diskrete Werte, aber wir wissen, was gemeint ist).
edit: Ich habe nicht richtig geguckt. HarteWare steigt ja nur dann ab, wenn die Zahl lokal nicht passt. In dem Fall ist auch er bei Zufallszahlen bei O(1). Dann passt meine Behauptung nicht und sein Vorgehen ist tatsächlich stets besser.