Ik heb deze formule uit een datastructuurboek in het bellensorteeralgoritme.
Ik weet dat we (n-1) * (n keer) zijn, maar waarom deling door 2?
Kan iemand mij dit uitleggen of het gedetailleerde bewijs hiervoor geven.
Bedankt
Antwoord 1, autoriteit 100%
Zie driehoeksgetallen.
Antwoord 2, autoriteit 91%
(N-1) + (N-2) +...+ 2 + 1
is een som van N-1 items. Herschik nu de items zo, dat na de eerste de laatste komt, dan de tweede, dan de op één na laatste, dwz (N-1) + 1 + (N-2) + 2 +..
. Aan de manier waarop de items nu zijn geordend, kunt u zien dat elk van die paren gelijk is aan N (N-1+1 is N, N-2+2 is N). Aangezien er N-1 items zijn, zijn er (N-1)/2 dergelijke paren. Dus je voegt N (N-1)/2 keer toe, dus de totale waarde is N*(N-1)/2
.
Antwoord 3, autoriteit 96%
Begin met de driehoek…
*
**
***
****
tot nu toe 1+2+3+4. Snijd de driehoek doormidden langs één dimensie…
*
**
* **
** **
Draai het kleinere deel 180 graden en plak het op het grotere deel…
**
*
*
**
**
**
Sluit de opening om een rechthoek te krijgen.
Op het eerste gezicht werkt dit alleen als de basis van de rechthoek een even lengte heeft – maar als deze een oneven lengte heeft, knip je gewoon de middelste kolom doormidden – het werkt nog steeds met een half-eenheid-brede twee keer zo grote -tall (nog steeds integer gebied) strook aan één kant van je rechthoek.
Wat de basis van de driehoek ook is, de breedte van uw rechthoek is (base / 2)
en de hoogte is (base + 1)
, geef ((base + 1) * base) / 2
.
Mijn base
is uw n-1
, aangezien de bubble-sorteer een paar items tegelijk vergelijkt en daarom alleen (N-1) herhaalt posities voor de eerste lus.
Antwoord 4, Autoriteit 114%
Probeer paren van cijfers uit de set te maken. De eerste + de laatste; de tweede + die voor het laatst. Het betekent N-1 + 1; N-2 + 2. Het resultaat is altijd n. En aangezien u twee cijfers bij elkaar toevoegt, zijn er alleen (N-1) / 2 paren die kunnen worden gemaakt van (N-1) nummers.
Zo is het als (n-1) / 2 * n.
Antwoord 5, Autoriteit 71%
Ik weet dat we (n-1) * (n keer) zijn, maar waarom de divisie met 2?
Het is alleen (n - 1) * n
Als u een naïef bubblesort gebruikt. U kunt een belangrijke besparingen krijgen als u het volgende opmerkt:
-
Na elke vergelijking-en-swap is het grootste element dat u bent tegengekomen op de laatste plek waar u was.
-
Na de eerste pas zal het grootste element in de laatste positie zijn; Na de K TH sup>PASS, staat het grootste element K TH sup>in de laatste positie K TH sup>.
U hoeft dus niet elke keer het hele ding te sorteren: u hoeft alleen N – 2 elementen de tweede keer door, N – 3 elementen de derde keer te sorteren, enzovoort. Dat betekent dat het totale aantal vergelijking / swaps u moet doen is (n - 1) + (n - 2) + ...
. Dit is een rekenkundige series en de vergelijking voor het totale aantal tijden is (n – 1) * n / 2.
Voorbeeld: Als de grootte van de lijst n = 5 is, dan doe je 4 + 3 + 2 + 1 = 10 swaps – en merk op dat 10 hetzelfde is als 4 * 5 / 2.
Antwoord 6, Autoriteit 29%
Som van de rekenkundige progressie
(A1 + A) / 2 * N = (1 + (N-1)) / 2 * (N-1) = N * (N-1) / 2
Antwoord 7, Autoriteit 29%
Dit is een vrij algemeen bewijs. Een manier om dit te bewijzen is om wiskundige inductie te gebruiken. Hier is een link: http://zimmer.csufresno.edu/ ~Larryc / Proofs/proofs.mathindectie.html
Antwoord 8, Autoriteit 14%
Neem aan N = 2 aan. Dan hebben we 2-1 = 1 aan de linkerkant en 2 * 1/2 = 1 aan de rechterkant.
duiden op f (n) = (n-1) + (n-2) + (N-3) + … + 1
Neem nu aan dat we tot n = k zijn getest. Dan moeten we testen voor n = k + 1.
Aan de linkerkant hebben we K + (K-1) + (K-2) + … + 1, dus het is f (k) + k
Aan de rechterkant hebben we vervolgens (k + 1) * k / 2 = (k ^ 2 + k) / 2 = (k ^ 2 + 2k – k) / 2 = k + (k-1) K / 2 = k f (k)
Dus dit moet voor elke k vasthouden, en dit concludeert het bewijs.
Antwoord 9
Hier is een bewijs door inductie, overweegt u N
termen, maar het is hetzelfde voor N - 1
:
Voor N = 0
De formule is natuurlijk waar.
Stel dat 1 + 2 + 3 + ... + N = N(N + 1) / 2
true is voor een natuurlijk N
.
We bewijzen 1 + 2 + 3 + ... + N + (N + 1) = (N + 1)(N + 2) / 2
is ook waar door onze eerdere veronderstelling:
1 + 2 + 3 + ... + N + (N + 1) = (N(N + 1) / 2) + (N + 1)
.
= (N + 1)((N / 2) + 1)
= (N + 1)(N + 2) / 2
Dus de formule bevat voor alle N
.