2011-12-01T13:38:34 pq

der unterschied ist glasklar.
über die elemente laufen und sich was merken ist O(n logn).
sortieren ist O(n * log n) (mergesort).

Oh, dann hatte ich unrecht. Ich dachte, Sortieren geht nie unter O(n^2) und wenn einmal sortiert ist, dauert die Suche O(n) (bzw O(n logn) ). Nichts desto trotz, je nach Anzahl der Elemente ist ab einem n_i dann log n_i > 2, sodass O(n logn) > O(2n), also ab einer bestimmten Groesse muesste das Sortieren laenger dauern, als das zweimalige Durchlaufen.