Ich versuche, die kleinste und zweitkleinste Zahl in einem Array zu finden. Ich kann zweimal oder einmal mit zwei Vergleichen scannen. Welches ist effizient?
2 Antworten
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.
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)
Verwandte Fragen
Neue Fragen
loops
Schleifen sind eine Art Kontrollflussstruktur in der Programmierung, bei der eine Reihe von Anweisungen wiederholt ausgeführt werden kann, bis eine bestimmte Bedingung erfüllt ist.