Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Praktische Informatik » 2Sum Algorithmus Laufzeitanalyse » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen 2Sum Algorithmus Laufzeitanalyse
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
Kim Kartrashian
unregistriert
2Sum Algorithmus Laufzeitanalyse Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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?
21.12.2019 21:56
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Praktische Informatik » 2Sum Algorithmus Laufzeitanalyse