Algorithmen & Datenstrukturen · Wie schnell ist schnell?
Eine Million Songs
Deine Musik-App soll prüfen, ob in einer Playlist ein Song doppelt vorkommt. Der erste Einfall: jeden Song mit jedem anderen vergleichen.
def hat_duplikat(songs):
for i in range(len(songs)):
for j in range(i + 1, len(songs)):
if songs[i] == songs[j]:
return True
return FalseBei 10 Songs ist das sofort fertig. Bei einer Million Songs rechnet dein Laptop Stunden. Warum? Um das zu verstehen, misst man nicht Sekunden (die hängen vom Gerät ab), sondern zählt Schritte: Wie oft läuft die innerste Zeile, wenn die Eingabe wächst?