---

Geschrieben von Kim Kartrashian am 21.12.2019 um 21:56:

  2Sum Algorithmus Laufzeitanalyse

Ich habe leider nicht besonders viel Ahnung von Laufzeitanalyse, allerdings eine ungefähre Vorstellung, wie schnell Routinen im praktischen Einsatz laufen. Hier soll es um den 2Sum-Algorithmus gehen. Folgende Fassung habe ich bei leetcode[dot]com gefunden:

code: 1: 2: 3: 4: 5: 6: 7: 8: def twoSum(nums, target): seen = {} for i, v in enumerate(nums): remaining = target - v if remaining in seen: yield [seen[remaining], i] seen[v] = i return []

Für die entsprechende Java-Fassung sind Laufzeitkomplexität mit O(n) und Speicherkomplexität mit O(n) angegeben. Ich habe diese Fassung insofern geändert, dass sie nicht nach dem ersten Fund abbricht, sondern alle Möglichkeiten ausgibt.

Ich habe meine eigene Fassung etwas abgewandelt erstellt:

code: 1: 2: 3: 4: 5: 6: 7: 8: def twosum(nums, target): c = 0 for i, v in enumerate(nums[:-1]): diff = target - v if diff in nums[i+1:]: yield (v, diff) c += 1 return c

Die Sequenz aus zur Verfügung stehenden Zahlen muss vor Nutzung sortiert werden, soll aber hier keine Rolle spielen. "c" ist der Zähler der die möglichen Paare zählt.

Grundsätzlich denke ich, bin aber alles andere als sicher, dass die Speicherkomplexität bei O(1) liegt. Aber die Zeitkomplexität? Keine Ahnung. Könnte mir da jemand weiterhelfen?

---

Geschrieben von spazzpp2 am 09.03.2020 um 15:17:

  RE: 2Sum Algorithmus Laufzeitanalyse

In beiden Varianten wird die Schleife in Zeile 3 immer voll durchlaufen, da sie in keinem Fall abgebrochen wird.

Die Fallunterscheidung vor yield entscheidet lediglich darüber, ob für das aktuelle nums-Element eine Ausgabe erfolgen soll, oder nicht.

Am Rande: Hast du diesen Code getestet? Bin mir gerade unsicher, was passiert, wenn diese Generator-Funktion (wegen enthaltenem yield) das Return erreicht und was sie dann zurückgibt. Scheint mir kein guter Stil zu sein.