Pages: [1]   Go Down
Print
Author Topic: Complessità SelectionSort(Confronti)  (Read 2590 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Jimmy93
Matricola
*
Offline Offline

Posts: 74



« on: 21-09-2013, 10:12:24 »

Non capisco questo passaggio:
\fs{4}\displaystyle\sum_{i=0}^{n-2}\left(1+\sum_{j=i+1}^{n-1}1 \right) = (n-1) + \sum_{i=0}^{n-2}(n-1-i)

Qualcuno può aiutarmi??  testate

EDIT del mod: questo forum supporta LaTeX. Usa questo invece di linkare siti esterni ;-)
« Last Edit: 21-09-2013, 11:02:38 by ɹǝǝuıƃuǝsɹǝʌǝɹ » Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.474


Più grande è la lotta, e più è glorioso il trionfo


WWW
« Reply #1 on: 21-09-2013, 11:24:45 »

\fs{4}\displaystyle\sum_{i=0}^{n-2}\left(1+\sum_{j=i+1}^{n-1}1 \right) =\sum_{\(A\)i=0}^{\(B\)n-2}{\({1}\)}+\sum_{i=0}^{n-2}{\({\sum_{\(C\)j=i+1}^{\(D\)n-1}{\({1}\)}}\)}\\=\overbrace{\({\({n-2}\)-0+1}\)}^ {B-A+1}+\sum_{i=0}^{n-2}\overbrace{\({\({n-1}\)-\({i+1}\)+1}\)}^{D-C+1}= \({n-1}\) + \sum_{i=0}^{n-2}\({n-1-i}\) ok
Logged

La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.

In tutto, amare e servire.

  
                            ن                           
I can deal with ads,
I can deal with buffer,
but when ads buffer
I suffer...

...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda...

   YouTube 9GAG    anobii  S  Steam T.B.o.I. Wiki [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
Jimmy93
Matricola
*
Offline Offline

Posts: 74



« Reply #2 on: 21-09-2013, 15:43:47 »

[latex] ok

Grazie ho capito, ma precisamente dove posso usare questa proprietà: \sum_{A}^{B}x = (B-A+x) ?? Sempre se è una proprietà XD
« Last Edit: 21-09-2013, 18:37:57 by ɹǝǝuıƃuǝsɹǝʌǝɹ » Logged
Jimmy93
Matricola
*
Offline Offline

Posts: 74



« Reply #3 on: 21-09-2013, 16:19:07 »

P.S Mentre aspetto risposta, il pasaggio successivo a quello che abbiamo visto sarebbe : \displaystyle(n-1)+(\sum_{i=0}^{n-2}n-\sum_{i=0}^{n-2}i-\sum_{i=0}^{n-2}(-1)) ??
« Last Edit: 21-09-2013, 18:44:16 by ɹǝǝuıƃuǝsɹǝʌǝɹ » Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.474


Più grande è la lotta, e più è glorioso il trionfo


WWW
« Reply #4 on: 21-09-2013, 18:44:01 »

[latex] ok

Grazie ho capito, ma precisamente dove posso usare questa proprietà: \sum_{A}^{B}x = (B-A+x) ?? Sempre se è una proprietà XD
La proprietà che ho usato non è quella che hai scritta tu, che non è nemmeno una proprietà visto che è falsa.

Ho sfruttato questa, piuttosto:
\fs{4}\displaystyle\sum_{i=A}^{i=B}\({k}\)=(B-A+1)\cdot\({k}\), ove \fs{3}k è una quantità che non dipende da \fs{3}i . Nel tuo caso \fs{3}k=1 quindi non si vede nella moltiplicazione. Quel "+1" tra parentesi devi vederlo così:

se per esempio dovessi sommare un certo numero di termini tutti uguali a k, diciamo da i=1 a i=10 (inclusi), noteresti che ci sono esattamente 10 elementi uguali a k. Se sommassi da i=21 a i=25 (inclusi), noti che ci sono 5 elementi.
Ora, ovviamente il numero di oggetti compresi tra due indici ha certamente una relazione con la loro differenza (10-1 e 25-21) solo che se fai la semplice differenza, stai scartando anche il primo indice (il più basso, cioè 1 oppure 21), quindi devi aggiungere un "+1" alla differenza. Tutto ciò puoi dimostrarlo per induzione, ma a questo livello lo si dà per scontato...
Logged

La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.

In tutto, amare e servire.

  
                            ن                           
I can deal with ads,
I can deal with buffer,
but when ads buffer
I suffer...

...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda...

   YouTube 9GAG    anobii  S  Steam T.B.o.I. Wiki [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.474


Più grande è la lotta, e più è glorioso il trionfo


WWW
« Reply #5 on: 21-09-2013, 18:49:52 »

P.S Mentre aspetto risposta, il pasaggio successivo a quello che abbiamo visto sarebbe : [latex]
No. Devi fare attenzione!

O lasci il generico addizionatore "+" tra le varie sommatorie, quando scomponi la sommatoria di un termine che è anch'esso una somma, e mantieni l'eventuale segno "-" dentro l'argomento della sommatoria scomposta, oppure lo fai uscire fuori dal segno di sommatoria, perché hai effettivamente fatto uscire un (-1) che moltiplicava l'argomento, e (-1), essendo costante, non dipende dalla variabile della sommatoria (i), e poteva uscire.

Diventerebbe, quindi:
\fs{4}\displaystyle(n-1)+\({\sum_{i=0}^{n-2}n+\sum_{i=0}^{n-2}\({-i}\)+\sum_{i=0}^{n-2}\({-1}\)}\)=(n-1)+\({\sum_{i=0}^{n-2}n-\sum_{i=0}^{n-2}i-\sum_{i=0}^{n-2}1}\)

Ora, le sommatorie sono tutte notevoli, quindi si semplificano facilmente. Ti anticipo che alla fine del processo di semplificazione otterrai un polinomio di secondo grado a coefficienti razionali a tre termini  ok.
Logged

La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.

In tutto, amare e servire.

  
                            ن                           
I can deal with ads,
I can deal with buffer,
but when ads buffer
I suffer...

...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda...

   YouTube 9GAG    anobii  S  Steam T.B.o.I. Wiki [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
Jimmy93
Matricola
*
Offline Offline

Posts: 74



« Reply #6 on: 22-09-2013, 10:10:05 »

Grazie, immaginavo che avrei detto un mucchio di cavolate  univ
Comunque sono arrivato a questo: \left( n(n-1)-\frac{(n-2)(n-1)}{2} - (n-1) \right)
c'è scritto così anche nelle slide del prof, quindi penso sia così XD, sono arrivato a questo punto applicando la proprietà che mi hai fatto vedere alla prima e terza sommatoria e la formula(si chiama così?? XD) di Gauss alla seconda(proprio di questa non ne sono sicuro al 100%). Mi potresti dire se è giusta o sbagliata?? 
« Last Edit: 22-09-2013, 11:34:49 by ɹǝǝuıƃuǝsɹǝʌǝɹ » Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.474


Più grande è la lotta, e più è glorioso il trionfo


WWW
« Reply #7 on: 22-09-2013, 11:36:26 »

Ciò che hai scritto corrisponde a ciò che è dentro la parentesi con le 3 sommatorie, corretto .

Non ricordo sinceramente se si chiamasse formula di Gau§ o altri nomi, io ero riusciuto a trovare la ricorrenza per la somma centrale già a scuola media/primo superiore mi pare, da solo pray...
Logged

La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.

In tutto, amare e servire.

  
                            ن                           
I can deal with ads,
I can deal with buffer,
but when ads buffer
I suffer...

...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda...

   YouTube 9GAG    anobii  S  Steam T.B.o.I. Wiki [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
Jimmy93
Matricola
*
Offline Offline

Posts: 74



« Reply #8 on: 22-09-2013, 12:15:29 »

Ciò che hai scritto corrisponde a ciò che è dentro la parentesi con le 3 sommatorie, corretto .

Non ricordo sinceramente se si chiamasse formula di Gau§ o altri nomi, io ero riusciuto a trovare la ricorrenza per la somma centrale già a scuola media/primo superiore mi pare, da solo pray...
Si è il risultato delle tre sommatorie, praticamente una sommatoria che va da i=0 a n di i si calcola con n(n+1),
visto che n = n-1 allora dovrebbe essere n-1(n-1+1) quindi n(n-1).
P.s Mi dispiace ma Gauss ti ha anticipato, non so se lo conosci ma questo è il suo famoso aneddoto XD : http://mategame.blogspot.it/2008/08/famosissimo-aneddoto-su-gauss.html
Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.474


Più grande è la lotta, e più è glorioso il trionfo


WWW
« Reply #9 on: 23-09-2013, 09:36:34 »

Proprio come ho fatto io pray...
Logged

La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.

In tutto, amare e servire.

  
                            ن                           
I can deal with ads,
I can deal with buffer,
but when ads buffer
I suffer...

...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda...

   YouTube 9GAG    anobii  S  Steam T.B.o.I. Wiki [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
Pages: [1]   Go Up
Print
Jump to: