Was ist schneller beim Suchen eines eindeutigen Maximums

[algorhtm]

Problem: Gegeben eine Liste von Zahlen, finde heraus, ob das Maximum der Liste genau einmal vorkommt.

Lösung 1: Sequentielles Durchsuchen fürs Bestimmen des Maximums, danach durchsuchen, ob dieses genau 1-mal vorkommt. Kosten 2n.

Lösung 2: Sortieren der Liste, danach schauen, ob das erste und zweite Element gleich sind: n log(n)

=> 1 ist besser?

[icarus2]

Loesung 1 ist schneller.

Btw: Du brauchst die Liste nicht zwei mal zu durchlaufen wenn du es etwas clever implementierst. Ein einziger Durchlauf muesste genuegen.

[SeppJ]

algorhtm schrieb:

=> 1 ist besser?

Was für eine Frage. Du hast es doch schon gezeigt. Sogar deutlich!

Die Angabe 2n als Komplexitätsklasse macht übrigens wenig keinen Sinn.

Und du kannst das natürlich noch verbessern, indem du gleich beim ersten Mal durchgehen mitzählst, wie oft das Maximum vorkommt, das halbiert nochmal die Konstante.