Ich versuche, die kleinste und zweitkleinste Zahl in einem Array zu finden. Ich kann zweimal oder einmal mit zwei Vergleichen scannen. Welches ist effizient?

0
Gopal Goel 29 Dez. 2015 im 19:13

2 Antworten

Beste Antwort

Ein Scan sollte schneller sein, da Sie nur zwei separate Variablen für die kleinste und die zweitkleinste beibehalten können. Sie verwenden im Durchschnitt weniger als zwei Vergleiche pro Iteration (im Vergleich zu 2x getrennten Schleifen, die genau 2x Einzelschleifenvergleiche verwenden).

In einer Art Pseudocode

smallest = Inf
2ndSmallest = Inf
for elem in array
    if elem < smallest
        2ndSmallest = smallest
        smallest = elem
    else if elem < 2ndSmallest
        2ndSmallest = elem
    end
end

Wenn dies voraussetzt, dass Sie die obigen if-Klauseln mindestens zweimal eingeben (Sie können problemlos einen Fix für Fälle hinzufügen, in denen dies möglicherweise nicht der Fall ist). Die Diskussion war jedoch zu bevorzugen, daher überlasse ich es Ihnen, die eigentliche Vergleichsimplementierung als Übung aufzuschreiben.

1
dfrib 29 Dez. 2015 im 16:58

Faustregel: Vermeiden Sie mehrere Schleifen

Zweite Faustregel: Vermeiden Sie vorzeitige Optimierung (zuerst lesbar und wartbar)

Das heißt, Pseudocode für einen effizienten Algorithmus

(Beachten Sie, dass Sie den Fall behandeln müssen, in dem die Listengröße leer oder eins ist):

smallest = min(list[0],list[1])
second_smallest = max(list[0],list[1])
for el in list[2:]:
    if el < second_smallest:
        second_smallest = max(el,smallest)
        smallest = min(el,smallest)
0
Harrichael 29 Dez. 2015 im 16:28