Programm mit Berechnung N über k, Laufzeit?
Kann mir hier jemand grob etwas über die Laufzeit für die Berechnung von N über k sagen?
Mein N ist z.B. 50 und ich möchte, dass das Programm alle Möglichkeiten berechnet für k=2, k=3, ... , k=49.
Ich habe es noch nicht ausprobiert und kann nicht einschätzen, wie lange so ein Programm für die ganzen Berechnungen benötigen würde.
Programmiersprache wäre Python.
3 Antworten
Die Laufzeit hängt natürlich stark vom verwendeten Algorithmus ab. Wenn man das ungefähr so macht
N = 50
binom = 1
for k in range(1, N):
binom = binom * (N+1-k) // k
print(k, binom)
benötigt man 49 Schleifendurchläufe und in jedem Durchlauf 4 Ganzzahloperationen. Das ist nicht viel. Das dauert auf einem normalen Computer keine Sekunde (Die Ausgabe ist vermutlich langsamer als die Berechnung).
Man benötigt kein Array und die Zahlen bleiben alle weit unter n! Python (>=3) kann mit beliebig großen Ganzzahlen umgehen. Es kann aber sein, dass sehr große Zahlen die Laufzeit negativ beeinflussen.
Alle möglichen Kombinationen stellst Du am besten durch eine Zahl 0≤m<2ⁿ dar. Jedes Bit entspricht dabei einem Element Deiner Grundmenge:
M = (2, 5, 7)
for m in range(2**len(M)):
print(", ".join(str(M[b])
for b in range(M)
if m&(2**b)))
Aber Vorsicht: Für N=50 gibt es schon über eine Billiarde Teilmengen. Die willst Du sicher nicht alle einzeln anschauen.
Ehm, da stimmt aber irgendwas nicht? Denn bei mir funktioniert das ganze nicht
Oh cool, gibt es auch eine einfache Möglichkeit, dass die einzelnen Kombinationen miteinander addiert werden und durch 2 geteilt werden? :D
Ach so! Ich dachte an "(2, 7)+(5, 7)=(2, 7, 5, 7)" oder so ...
for m in range(2**len(M)):
sum(M[b] for b in range(len(M)) if m&(2**b))) / 2
Es gilt ( n über k ) = n! / (k! (n-k)!)
Um diesen Ausdruck für alle k = 1,...n berechnen zu können, braucht man ein Array der Länge n mit Array(k) = k!
Um das Array aufzubauen, benötigt man nur n Multiplikationen, weil man rekursiv auf das Vorgänger-Element zurückgreifen kann.
Ist das Array aufgebaut, braucht man für den obigen Term eine Multiplikation für den Nenner und eine Division für den Bruch:
(n über k) = Array(n) / (Array(k) * Array(n-k))
Die Laufzeit ist somit für kleine n verschwindend gering.
Die Laufzeit wird eventuell nur dann beinträchtigt, wenn ein 64 Bit Integer nicht mehr reicht, um n! darstellen zu können.
Man muss dann eine andere Integer-Arithmetik nutzen. Ich kann mir aber nicht vorstellen, dass die Laufzeit aufgrund der wenigen Operationen beträchtlich ansteigt.
Einfach mal für kleine n ausprobieren. Die Laufzeit kann man dann linear hochrechnen, denn die Berechnung für z.B. (2n)! dauert doppelt solange wie die für n!
Für math.comb(n, k) braucht es k Operationen. Um alle 0≤k≤n zu berechnen, braucht es daher 𝓞(n²) Operationen.
Eine Operation ist hier eine Integer-Multiplikation und -Division. Das dauert bei b Bits theoretisch b Schritte. Da alle Werte unter 2ⁿ liegen, kann man die Laufzeit insgesamt mit 𝓞(n³) abschätzen.
Auf meiner alten Kiste messe ich:
- für n=⠀4000: ca. ⠀5 Sekunden
- für n=⠀6000: ca. 15 Sekunden
- für n=⠀8000: ca. 36 Sekunden
- für n=10000: ca. 75 Sekunden
Das wären also ungefähr T(n)=75·10⁻¹²·n³ [s]. Für n=100.000 ergäbe sich damit eine Laufzeit von 75.000 s ≈ 21 h.
Weißt du vielleicht wie ich mir auch alle möglichen Kombinationen anzeigen lassen kann?
Habe z.B. die Werte (2, 5, 7), also N=3
und damit die Möglichkeiten:
(2), (5), (7), (2, 5), (2, 7), (5, 7) und (2, 5, 7)