Was ist der Beweis von (N–1) + (N–2) + (N–3) + ... + 1= N*(N–1)/2
Ich habe diese Formel von einer Datenstruktur Buch in der bubble-sort-Algorithmus.
Weiß ich, dass wir (n-1) * (n-mal), aber warum die division durch 2?
Kann jemand bitte erklären Sie mir oder geben Sie die detaillierten Beweis dafür.
Danke
InformationsquelleAutor der Frage skystar7 | 2010-03-20
Du musst angemeldet sein, um einen Kommentar abzugeben.
Sehen Dreieck-zahlen.
InformationsquelleAutor der Antwort Viral Shah
Start mit dem Dreieck...
vertreten 1+2+3+4 so weit. Schneiden Sie das Dreieck in der Hälfte entlang einer dimension...
Drehen Sie den kleineren Teil um 180 Grad, und kleben Sie es oben auf dem größeren Teil...
Schließen Sie die Lücke zu einem Rechteck.
Auf den ersten Blick funktioniert dies nur, wenn die Basis des Rechtecks hat noch die Länge - aber wenn es eine ungerade Länge haben, die Sie gerade schneiden die mittlere Spalte in der Hälfte - es funktioniert immer noch mit einer halb-Einheit-weit doppelt so hoch (noch integer-Bereich) Streifen auf einer Seite des Rechtecks.
Was auch immer die Basis des Dreiecks, die Breite des Rechtecks ist
(base /2)
und die Höhe ist(base + 1)
geben((base + 1) * base) /2
.Aber, meine
base
ist Ihren-1
da die bubble-sort vergleicht ein paar Artikel zu einem Zeitpunkt, und daher durchläuft nur (n-1) - Positionen für die erste Schleife.InformationsquelleAutor der Antwort Steve314
(N-1) + (N-2) +...+ 2 + 1
ist eine Summe von N-1 Elemente. Nun ordnen Sie die Elemente so, dass nach dem ersten kommt der Letzte, dann die zweite, dann die vorletzte, also(N-1) + 1 + (N-2) + 2 +..
. Die Art und Weise die Elemente sind bestellt, nun sehen Sie, dass jedes dieser Paare ist gleich N (N-1+1 ist N, N-2+2 N). Da gibt es N-1 Elementen gibt es (N-1)/2 solche Paare. Du bist also der Zugabe von N (N-1)/2 mal, so dass der Gesamtwert istN*(N-1)/2
.InformationsquelleAutor der Antwort sepp2k
Versuchen, um Paare von zahlen aus der Menge. Die erste + die Letzte; die zweite + der vorletzte. Es bedeutet, dass n-1 + 1, n-2 + 2. Das Ergebnis ist immer n ist. Und da Sie das hinzufügen von zwei zahlen zusammen, es gibt nur (n-1)/2 Paare, die gemacht werden können von (n-1) zahlen.
Also es ist wie (N-1)/2 * N.
InformationsquelleAutor der Antwort gius
Es ist nur
(n - 1) * n
wenn Sie einen naiven bubblesort. Können Sie eine erhebliche Einsparungen, wenn Sie Folgendes bemerken:Nach jedem compare-and-swap -, das größte element, das Sie erlebt haben, werden in der letzten Stelle, die Sie waren.
Nach dem ersten Durchlauf das größte element an der letzten position; nach der kth übergeben, die kth größte element in der kth Letzte position.
Damit Sie nicht zu Sortieren, die ganze Sache jedes mal: Sie brauchen nur zu Sortieren, n - 2 Elemente, die das zweite mal über n - 3 Elemente der Dritten Zeit, und so weiter. Das bedeutet, dass die Gesamtzahl der Vergleiche/swaps, die Sie tun müssen, ist
(n - 1) + (n - 2) + ...
. Dies ist ein arithmetische Reiheund die Gleichung für die Summe der Zeiten ist (n - 1)*n /2.Beispiel:wenn die Größe der Liste ist N = 5, dann tun Sie 4 + 3 + 2 + 1 = 10 swaps -- und bemerken, dass 10 ist die gleiche wie 4 * 5 /2.
InformationsquelleAutor der Antwort John Feminella
Dies ist eine ziemlich häufige Beweis. Eine Möglichkeit, dies zu beweisen, ist die Verwendung der mathematischen Induktion. Hier ist ein link: http://zimmer.csufresno.edu/~larryc/proofs/proofs.mathinduction.html
InformationsquelleAutor der Antwort John Kane
Summe der arithmetischen progression
(A1+AN)/2*N = (1 + (N-1))/2*(N-1) = N*(N-1)/2
InformationsquelleAutor der Antwort ShPavel
Übernehmen n=2. Dann haben wir 2-1 = 1 auf der linken Seite und 2*1/2 = 1 auf der rechten Seite.
Bezeichnen f(n) = (n-1)+(n-2)+(n-3)+...+1
Nun davon aus, dass wir getestet haben, bis n=k. Dann haben wir einen test für n=k+1.
auf der linken Seite haben wir k+(k-1)+(k-2)+...+1, also ist f(k)+k
Auf der rechten Seite haben wir dann (k+1)*k/2 = (k^2+k)/2 = (k^2 +2k - k)/2 = k+(k-1)k/2 = kf(k)
Also das musst halt für jedes k, und dies beendet den Beweis.
InformationsquelleAutor der Antwort martiert
Hier ist ein Beweis durch Induktion, wenn man bedenkt
N
Bedingungen, aber es ist das gleiche fürN - 1
:Für
N = 0
die Formel stimmt offensichtlich.Angenommen
1 + 2 + 3 + ... + N = N(N + 1) /2
gilt auch für einige natürlichenN
.Wir beweisen
1 + 2 + 3 + ... + N + (N + 1) = (N + 1)(N + 2) /2
ist auch wahr, durch die Nutzung unserer vorherigen Annahme:1 + 2 + 3 + ... + N + (N + 1) = (N(N + 1) /2) + (N + 1)
.= (N + 1)((N /2) + 1)
= (N + 1)(N + 2) /2
Also die Formel gilt für alle
N
.InformationsquelleAutor der Antwort IVlad