Python Zahlen einer Liste addieren um spezifisches Ergebnis zu erhalten?
Tut mir Leid für den Titel, ich kann es leider nicht kurz beschreiben.
Ich suche eine Funktion in Python, mit deren Hilfe ich aus einer gegebenen Liste zwei Zahlen finden soll, die zusammen addiert 2021 ergeben. Diese dann im Anschluss noch multiplizieren. Mit dieser Hilfe soll ich dann schlussendlich beschreiben, wie ich die Zeitkomplexität dieses Beispiels berechnet habe.
Ich bin über jede Hilfe in dieser Sache sehr dankbar, da ich im Moment ziemlich am verzweifeln bin.
3 Antworten
Am einfachsten geht das, indem du die Liste zu einem Set umwandelst, und dann nach Duplikaten in einer Liste suchst, in der die benötigten Zahlen stehen:
numbers = [... deine Zahlen ...]
numbers2 = [2021 - x for x in numbers]
result = list(set(numbers).intersection(numbers2))
Laufzeit natürlich O(n).
Oder, alternativ, falls der Overhead von der Set-Konvertierung zu groß ist, könnte man auch einen solchen O(n * log(n)) Algorithmus benutzen:
numbers = [... deine Zahlen ...]
sum = 2021
left = 0; right = len(numbers)-1
numbers.sort()
while left != right:
if sum - numbers[left] == numbers[right]:
break
elif sum - numbers[left] < numbers[right]:
right-=1
else:
left += 1
if left != right:
print(numbers[left], numbers[right])
else:
print("Kein geeignetes Paar gefunden")
Zeitkomplexität der Schleife ist n. Zeitkomplexität des sortierens (sort()) ist n * log(n). Folglich ist die Zeitkomplexität der gesamten Funktion das größere von beiden, nämlich n * log(n).
Wieso die Zeitkomplexität der gesamten Funktion auf das Sortieren beschränkt ist, erschließt sich mir nicht ganz.
O(n) + O(n * log(n)) = O(n * log(n)).
Beim Addieren von Zeitkomplexitäten lässt man die kleineren einfach wegfallen, da sie bei einem hohen n nur einen kleinen unbedeutenden Unterschied machen.
und danach musst du trotzdem noch mal potentiell jedes Element mit jedem vergleichen.
Nein, danach geht man die Liste einfach von Links und Rechts gleichzeitig durch, bis man in der Mitte ist oder ein Match hat. Worst Case O(1*n). Deswegen sortiert man sie vorher, sonst wäre das so nicht möglich.
O(n) + O(n * log(n)) = O(n * log(n)).
Ehm, nein. Diese Gleichung wäre nur erfüllt, wenn O(n) = 0.
Beim Addieren von Zeitkomplexitäten lässt man die kleineren einfach wegfallen, da sie bei einem hohen n nur einen kleinen unbedeutenden Unterschied machen.
Ein Satz den einer meiner Profs gerne von sich gegeben hat: "Da sieht man mal wieder, warum Mathematiker in der Informatik nichts verloren haben." ;-P
Wenn n gegen unendlich geht, dann wird die Teilmenge O(n) natürlich immer kleiner im Verhältnis zur Gesamtmenge.
Aber im Realismus gibt es die Unendlichkeit nicht. Es gibt keine unendlich großen Datensätze. Und nun nimm zwei Algorithmen die das Wetter simulieren sollen. Der eine hat eine Komplexität von O(n) + O(n * log(n)) und der andere von O(n * log(n)) - O(n).
Mit n gegen unendlich wären beide gleichwertig. Im Realismus würde man sich bei 1*10^9 Daten aber mit dem einen Beispiel gegenüber dem anderen 2*10^9 Durchläufe ersparen. Wenn der Computer pro Sekunde 250 000 Datensätze schafft, sprechen wir hier über einen Zeitunterschied von ~2 1/4 Stunden.
Deswegen wäre sowas an meiner Hochschule ein Verbrechen gewesen.
Nein, danach geht man die Liste einfach von Links und Rechts gleichzeitig durch, bis man in der Mitte ist oder ein Match hat.
Okay, wenn man einen Mergesort anwendet, dann dürfte die Variante tatsächlich die optimalste sein. Allerdings hätte er selbst darauf kommen sollen. Oder zumindest sich Gedanken dazu machen, wie man es lösen kann und dann entsprechend die Zeitkomplexität aufstellen. :)
Wir habens in der Hochschule im Fach Algorithmen und Datenstrukturen so gelernt, dass man die kleineren vernachlässigen kann und soll. Wenn ihr als Mathematiker das anders macht, von mir aus, aber ich werds weiterhin so machen wie es mir beigebracht wurde. :D
Eine Komplexität wie
3n^2 + 2
wird bei uns auch einfach zu O(n^2) vereinfacht.
Und ich denke das ist auch richtig so wie wir es gelernt haben, hab noch nie jemanden gesehen der es so macht wie du.
Wenn ihr als Mathematiker
Ich bin keine Mathematiker, ich bin Wirtschaftsinformatiker. Deine Interpretation wäre die mathematische, denn die "unbedeutende" Differenz tritt nur ein, wenn n gegen unendlich geht. Was macht es da schon, ob es nun 1.000.000.001 Jahre zur Berechnung sind oder nur 999.999.999 Jahre. ;-)
In der Praxis spielt das aber eben schon eine Rolle, weil der Zeitfaktor da alles ist! Wenn ein Programm das Wetter von morgen erst übermorgen errechnet hat, macht das schon einen Unterschied, wenn ein anderes es bereits heute Abend errechnet hat, denkst du nicht? ;-)
Eben deswegen sagte mein Prof ja immer, dass Mathematiker in der Informatik nichts verloren haben.
Variante 1 ist defunct, sofern es mehrere Paarungen gibt, weil keine Paare erzeugt werden. Du müßtest daraus dann noch ne sortierte Liste erzeugen, um die Paarungen zu identifizieren.
Ansatz zwei wäre wohl der rationale Weg.
Ich denke, es ist essentiell, dass du diese Aufgabe selbst bewerkstelligst. Ich gebe dir nur ein paar Gedankenstützen.
- Was muss man tun, um jedes Element in einer List mit allen anderen Elementen zu vergleichen?
- Wie viele Durchläufe sind demnach maximal notwendig? Verallgemeinert ausgedrückt.
- Unterscheiden sich die minimal notwendigen Durchläufe von den maximal notwendigen? Sprich, was passiert wenn du direkt beim ersten Vergleich zwei Zahlen gefunden hast, die addiert 2021 ergeben?
Wenn du das erste Element in der Liste mit allen anderen verglichen hast und du gehst über zum zweiten Element, vergleichst du das dann auch wieder mit dem ersten Element?
Natürlich nicht. Aber diese Denkaufgabe soll er ja selbst übernehmen...
Was nichts an n^2 ändert. Denn n+(n-1)+...+(n-n+1) bleibt quadratisch.
Ist das so?
Bei 10 Daten müssten das 100 sein. Wenn er nur noch die Folgeglieder berücksichtigt, sind es O(((n-1)² - (n-1))/2) = 36.
Wenn n gegen Unendlich geht, wird es also schlimmstenfalls 0,5n²
Und ich habe nirgends gesagt, dass man es nicht noch weiter verbessern könnte. Es geht nur darum, dass er selbst auf diese Gedankengänge kommt, denn das ist Zweck der Übung! Es durchzuspielen wie viel Durchgänge man benötigt, um zu bewerten, wie performant ein Algorithmus ist und dieses Denkschema zu verinnerlichen.
O(((n-1)² - (n-1))/2)
Ist das so?
Du vergleichst das 1. Element mit allen n-1 anderen, das 2. mit allen n-2 verbleibenden usw.
Das widerholst Du, bis Du beim vorletzen Element angekommen bist.
Ist das so?
Fast, es sind ((n² - n)/2), trotzdem wird es bei n gegen unendlich maximal auf 0,5n² hinauslaufen.
https://www.programiz.com/python-programming/online-compiler/
numbers = [1,2,3,4,5,6,7,8,9,10];
count = 0;
for i in range(len(numbers)-1):
for j in range(i+1,len(numbers)):
count += 1;
print(count);
Es sollte aber auch lediglich aufzeigen, dass eine kleine Änderung in der Schleifenkonstruktion die maximale Zeit bereits halbiert.
Und 0.5 n^2 liegt in O(n^2) mit dem konstanten Faktor c=0.5.
Sofern Du mir ein g(n) nennen kannst, sodaß c*n*g(n) 0.5n^2 deckelt, lasse ich mich auf O(n*g(n)) ein.
Bis dahin aber bleibe ich bei g(n)=n.
--------
Bei Vorsortierung klappt O(n log(n)), das betrachten wir aber derzeit ja nicht.
Und 0.5 n^2 liegt in O(n^2)
Alles <= n² liegt in O(n²). Also was ist dein Punkt?
Es nimmt quadratisch zu, aber eben halbiert. Das macht es immer noch nicht gut und sollte vermieden werden wenn möglich, aber es diente auch nur als Beispiel dafür, welches Denkschema er braucht.
Darüber hinaus hat der Code nachgewiesen, dass die Formel stimmt. Und diese ist ziemlich eindeutig:
- best case = 1
- average case = (n²-n)/4
- worst case = (n²-n)/2
Von daher bleibe ich bei < 0,5n² bis du mir das Gegenteil bewiesen hast. :)
auch alles <= c*n^2 liegt in O(n^2).
Und nein, Du hast lediglich gezeigt, daß Du 0.5n^2 mal eine bestimmte Anweisung ausführst ;-).
Daß dem linearen Faktor keine besondere Beachtung zuteil wird, machen wir nicht aus Spaß.
Ich habe gezeigt, dass ich in weniger als 0,5n² Durchläufen jede mögliche Summe mit 2 Zahlenpärchen aus dem Array gebildet habe.
Das war die Aufgabenstellung, wenn ich mich nicht täusche. Und egal wie groß das Array wird, es bleibt trotzdem weniger als 0,5n².
Und selbst wenn n gegen unendlich geht, dann wäre es immer noch mehr als doppelt so wie n². Als Mathematiker mag man da keinen Unterschied sehen, als Informatiker aber schon. Denn für uns ist Zeit etwas reales und daher Unendlichkeit keine Option!
Gut, dass wir drüber gesprochen haben...
Die Aufgabe war die Zeitkomplexität des Algorithmus zu bestimmen. Nicht die Anzahl der Durchläufe der inneren Schleife.
Du hast a+b*(n-1)+c*n*(n-1)/2. als Komplexität.
Oder eben O(n^2). Daß wir die 0.5 ignorieren, hat den gleichen Grund aus dem wir a,c und d ignorieren.
Machen wir es exemplarisch:
2^24=n
vs
3*2^27 = n log n
vs
2^48 = n^2
vs
5*2^47 = 0.5 n^2
----------
Bei der Komplexität soll die Güte bewertet werden, lineare Faktoren sind da nunmal eher belanglos. (Nicht umsonst ist es theoretische Informatik).
Übrigens liegt O(n^2) auch in O(0.5n^2).
Die Aufgabe war die Zeitkomplexität des Algorithmus zu bestimmen. Nicht die Anzahl der Durchläufe der inneren Schleife.
Wir bestimmen Zeitkomplexität immer mit der Anzahl der Durchläufe bzw. Operationen. O(n*log(n)) steht auch nicht für eine bestimmte Zeit, sondern für eine Anzahl, die man ggf. in Zeit umrechnen kann.
Und ich habe nicht nur die Durchläufe der inneren Schleife dargestellt, sondern die Anzahl der Operationen die es auf diese Art braucht, um jedes einzelne Element innerhalb einer Liste mit allen anderen zu addieren.
Und für dich mag es zwischen kleiner 0,5n² und n² keinen Unterschied geben. Aber wenn du gerne ein praxisrelevantes Beispiel haben möchtest:
Die Formel für den Anhalteweg wie wir in aus der Fahrschule kennen beträgt ca:
Anhalteweg in m = (0,1 * Geschwindigkeit in km/h) * (0,1 Geschwindigkeit in km/h)
Bei einer Geschwindigkeit von 50km/h also ca 25 m.
Nun kommt ein Informatiker daher und programmiert eine KI, wo durch der Anhalteweg nur noch halb so lange dauert.
Wenn dir bei der Geschwindigkeit ein Kind in 15 Meter Entfernung auf die Straße läuft, du also mit KI 2,5 Meter vor dem Kind zum Stehen kommst und ohne KI auch ein Notarzt nicht mehr rechtzeitig ankommt, dann würde ein Satz wie
Aber in der Mathematik macht das aber keinen Unterschied!
eher auf Unverständnis sorgen, denn in der Realität ist der Unterschied in diesem Beispiel kaum drastischer darzustellen!
Daher erneut: Nur Mathematiker vernachlässigen Faktoren mit der Begründung, dass ihr Einfluss in Richtung Unendlichkeit schwindet! Die Unendlichkeit hat nichts mit der Realität zu tun...!
Ich sehe schon, das bringt nichts.
Wir Informatiker bestimmen die Zeitkomplexität von Algorithmen indem wir uns die benötigten Rechenschritte anschauen, deren Komplexität wir wiederum nicht kennen. Vielmehr interessiert uns die Größenordnung des Wachstums in der Eingabegröße und dabei spielen lineare Faktoren eben keine Rolle. Punkt.
Nur Mathematiker vernachlässigen Faktoren mit der Begründung, dass ihr Einfluss in Richtung Unendlichkeit schwindet!
Nein, auch jeder Informatik-Professor, der das Thema Zeitkomplexität unterrichtet, wird dir da dasselbe sagen wie ich und KarlRanseierIII. Das machen nicht nur Mathematiker so. Dir wurde da wohl einfach Quatsch beigebracht, oder du hast nicht aufgepasst.
from itertools import combinations as comb
numbers = [1, 2, 3]
summed = 6
result = [(a, b) for a, b in comb(numbers) if a * b == summed]
print(result) # (2, 6)
Das liefert dir alle Zweier-Zahlenkombinationen aus der Liste "numbers", die in der Summe "6" ergeben.
In deinem Falle musst du also einfach nur die Variablen "numbers" und "summed" anpassen. In "result" stehen dann alle entspr. Kombinationen, und zwar ohne Doubletten! :)
Wieso die Zeitkomplexität der gesamten Funktion auf das Sortieren beschränkt ist, erschließt sich mir nicht ganz. Und auch der Vorteil des Sortierens bei dieser speziellen Aufgabe bleibt mir verborgen.
Im Grunde musst du so sogar 2x durch die Liste. Einmal um sie zu sortieren (n * log(n)) und danach musst du trotzdem noch mal potentiell jedes Element mit jedem vergleichen.
Also hast du im Grunde eine Zeitkomplexität erschaffen von:
O((n * log(n)) + (((n-1)² - (n-1)) / 2))
Oder habe ich einen Denkfehler? :)