2011-12-01T16:15:43 bianca

Einmal für das Größte und einmal für das Zweigrößte. Und ob man das mit einem um 1 verringerten Hash tut oder ob man stattdessen sort [1] nimmt bleibt doch annähernd gleich, oder nicht?

nun, ich versuche doch nur die komplexität der algorithmen klarzumachen. ein max() hat O(n) und ein mergesort o(n * log n).
wenn man also den weg geht, zweimal max anzuwenden, hat man eine komplexität von O(2n).

das ist zwar generell reduzierbar auf O(n), wenn man aber einen vergleichswert zu mergesort haben möchte bei einer ungefähren grösse von n, dann kann man O(2n) mit O(n * log n) vergleichen und feststellen, dass die beiden algorithmen bei n=10 ungefähr gleich gut abschneiden und bei 100 elementen der weg mit max() nur noch 43% der zeit von sort() braucht, was aber vermutlich absolut gesehen immer noch eine relativ geringe zahl ist.

wenn informatik sich immer auf "algorithmus A ist schneller als algorithmus B" reduzieren liesse, gäbe es sicher mehr informatiker.

wie ein algorithmus abschneidet, ist in erster linie von der eingabemenge abhängig, ggfs. auch von der art der eingabe (worst case szenario bei quicksort z.b.).

und dann ist es noch davon abhängig, wie oft das ganze in deinem programm vorkommt. desweiteren muss man in der realität oft auch noch speicherverbrauch mit beachten.


das heisst, da du hier null angaben machst über datenmenge etc, kann dir kein mensch sagen, was du verwenden solltest. ich sagte jedoch, dass es bei beispielsweise 100 elementen vermutlich ziemlich egal ist.
ich kann aber deine frage "bleibt doch annähernd gleich" nicht pauschal mit ja oder nein beantworten.
Last edited: 2011-12-01 17:36:59 +0100 (CET)