Ho ottenuto questa formula da una struttura dati prenota nell'algoritmo bubble sort.Qual è la prova di (N-1) + (N-2) + (N-3) + ... + 1 = N * (N-1)/2
So che siamo (n-1) * (n volte), ma perché la divisione per 2?
Qualcuno può spiegarmelo o fornirgli la dimostrazione dettagliata.
Grazie
Vedere triangle numbers.
Grazie Mi sono piaciute queste tecniche per spiegare la dimostrazione di questa formula in particolare la tecnica numero tre, che può essere trovato su http://betterexplained.com/articles/techniques-for-adding-the-numbers-1-to-100/ – skystar7
Provare a creare coppie di numeri dal set. Il primo + l'ultimo; il secondo + quello precedente. Significa n-1 + 1; n-2 + 2. Il risultato è sempre n. E dal momento che aggiungi due numeri insieme, ci sono solo (n-1)/2 coppie che possono essere fatte da (n-1) numeri.
quindi è come (N-1)/2 * N
Somma di progressione aritmetica
(A1 + AN)/2 * N = (1 + (N-1))/2 * (N-1) = N * (N-1)/2
So che siamo (n-1) * (n volte), ma perché la divisione per 2?
E 'solo (n - 1) * n se si utilizza un bubblesort ingenuo. È possibile ottenere un notevole risparmio se si nota quanto segue:
Dopo ogni confrontare-e-swap, il più grande elemento che hai riscontrato sarà l'ultimo posto foste a.
Dopo il primo passaggio, l'elemento più grande si troverà nell'ultima posizione; dopo il k th pass, il k th il più grande elemento sarà nel k th ultima posizione.
Quindi non c'è bisogno di ordinare il tutto ogni volta: è sufficiente ordinare n - 2 elementi la seconda volta attraverso, n - 3 elementi per la terza volta, e così via. Ciò significa che il numero totale di confronti/swap che devi fare è (n - 1) + (n - 2) + .... Si tratta di un arithmetic series, e l'equazione per il numero totale di volte è (n - 1) * n/2.
Esempio: se la dimensione della lista è N = 5, poi si fa 4 + 3 + 2 + 1 = 10 swaps - e notare che 10 è uguale a 4 * 5/2.
Ma è anche scritto che n (n - 1)/2 o O (n^2) o n^2. Quindi quadrato di n il quadrato di 5 è 25. Ma n (n-1)/2 è 10. Quindi come è possibile? – Harinder
@Harinder: "o O (n^2) o n^2 ...". No, O (n^2) == n^2 non è corretto. 'n^2 + 1,000,000' è anche' O (n^2) 'ma chiaramente non è uguale a' n^2'. –
Questo è quello che non capisco. Per esempio guarda questo http://www.sparknotes.com/cs/sorting/bubble/section1.rhtml. Dice anche che la media e la peggiore delle ipotesi sono n^2 – Harinder
(N-1) + (N-2) +...+ 2 + 1 è una somma di elementi N-1. Ora riordina gli elementi in modo che, dopo il primo arriva l'ultimo, poi il secondo, poi il penultimo, ovvero (N-1) + 1 + (N-2) + 2 +... Il modo in cui gli oggetti sono ordinati ora puoi vedere che ognuna di queste coppie è uguale a N (N-1 + 1 è N, N-2 + 2 è N). Dato che ci sono elementi N-1, ci sono (N-1)/2 tali coppie. Quindi stai aggiungendo N (N-1)/2 volte, quindi il valore totale è N*(N-1)/2.
Assumere n = 2. Quindi abbiamo 2-1 = 1 sul lato sinistro e 2 * 1/2 = 1 sul lato destro.
Denota f (n) = (n-1) + (n-2) + (n-3) + ...+1
Supponiamo ora di aver testato fino a n = k. Quindi dobbiamo testare per n = k + 1.
sul lato sinistro abbiamo k + (k-1) + (k-2) + ... + 1, quindi è f (k) + k
Sul lato destro abbiamo poi (k +1) * k/2 = (k^2 + k)/2 = (k^2 + 2k - k)/2 = k + (k-1) k/2 = k f (k)
Quindi questo deve valere per ogni k, e questo conclude la dimostrazione.
Ecco una dimostrazione per induzione, considerando N termini, ma è lo stesso per N - 1:
Per N = 0 la formula è ovviamente vero.
Supponiamo che 1 + 2 + 3 + ... + N = N(N + 1)/2 sia vero per alcuni naturali N.
Noi dimostreremo 1 + 2 + 3 + ... + N + (N + 1) = (N + 1)(N + 2)/2 vale anche utilizzando la nostra precedente ipotesi:
1 + 2 + 3 + ... + N + (N + 1) = (N(N + 1)/2) + (N + 1) = (N + 1)((N/2) + 1) = (N + 1)(N + 2)/2.
Quindi la formula vale per tutti N.
"Supponiamo che P (N) sia vero per tutta la N naturale". Questa non è una prova corretta per induzione. Stai cercando di dimostrare P (N) => P (N + 1), quindi dovresti assumere che P (N) sia vero per * alcuni * N. Se lo presumi per * all * N, allora fai la domanda . –
Questa è una prova abbastanza comune. Un modo per dimostrarlo è usare l'induzione matematica. Ecco un link: http://zimmer.csufresno.edu/~larryc/proofs/proofs.mathinduction.html
Inizia con il triangolo ...
*
**
***
****
che rappresenta 1 + 2 + 3 + 4 finora. Tagliare il triangolo a metà lungo una dimensione ...
*
**
* **
** **
Ruotare la parte minore di 180 gradi, e bastone sulla parte superiore della parte maggiore ...
**
*
*
**
**
**
Chiudere il gap per ottenere un rettangolo.
A prima vista funziona solo se la base del rettangolo ha una lunghezza uniforme - ma se ha una lunghezza dispari, basta tagliare la colonna centrale a metà - funziona ancora con una mezza unità di larghezza due volte - striscia alta (ancora intera) su un lato del rettangolo.
Qualunque sia la base del triangolo, la larghezza del rettangolo è (base/2) e l'altezza è (base + 1), dando ((base + 1) * base)/2.
Tuttavia, il mio base è il vostro n-1, poiché l'ordinamento di bolle confronta una coppia di articoli alla volta e quindi itera su solo (n-1) posizioni per il primo ciclo.
http://mathoverflow.net/ –
... è solo per domande di matematica a livello di ricerca. – rjh
@PascalThivent: questa domanda dovrebbe essere chiusa in pochi secondi su mathoverflow. – sepp2k