Insertion Sort...dubbio

[thefrog]

ho un dubbio...
l'insertion sort esegue lo stesso numero di confronti e di spostamenti....e fin qui ci siamo

però le dispense che ho sono ambigue.....danno 2 formule:

ne esegue (n*n)/4
oppure (((n*n)-n)/4)

??????

ditemelo o boccio l'esame

[mjordan]

Quelle formule non vanno interpretate in quel modo ma nell'ambito di una serie numerica.
La prima formula indica la serie numerica di j per j che va da 2 a n.
La seconda formula indica la serie numerica di (j - 1) per j che va da 2 a n.

Tali valori (quelli che hai dato tu) vanno sostituiti nell'analisi della complessità computazionale T(n), ottenendo, (stiamo parlando del caso peggiore) una complessità computazionale T(n)=O(n^2) evidenziando un andamento quadratico.

[mjordan]

Tu una Golf quarta serie con quasi 100.000 Km e per di più incidentata ci rivuoi 3000 euro?

[thefrog]

Originariamente inviato da mjordan
Quelle formule non vanno interpretate in quel modo ma nell'ambito di una serie numerica.
La prima formula indica la serie numerica di j per j che va da 2 a n.
La seconda formula indica la serie numerica di (j - 1) per j che va da 2 a n.

Tali valori (quelli che hai dato tu) vanno sostituiti nell'analisi della complessità computazionale T(n), ottenendo, (stiamo parlando del caso peggiore) una complessità computazionale T(n)=O(n^2) evidenziando un andamento quadratico.

ehm ehm....ok, io devo calcolare il Chi Quadro, quindi quale è quella corretta?

intanto grazie

[mjordan]

Il Chi quadro? E che roba è?
Se mi dai indicazioni + precise su dove hai tirato fuori quelle formule ti posso postare l'analisi computazionale completa. Anche se ci vorrebbe un forum Latex

[thefrog]

Originariamente inviato da mjordan
Il Chi quadro? E che roba è?
Se mi dai indicazioni + precise su dove hai tirato fuori quelle formule ti posso postare l'analisi computazionale completa. Anche se ci vorrebbe un forum Latex

il chi quadro è quel calcolo che ti permette di sapere, in una simulazione di un algoritmo,eseguito un TOT di volte, quanto i dati sperimentali si discostano da quelli teorici....tutto qua, niente di chissacchè....

vorrei semplicemente sapere quale di quelle 2 formule devo usare (n è il numero di elementi presenti nella struttura dati)

[mjordan]

Non ne avevo mai sentito parlare.

Ti avevo chiesto di quelle formule perchè a livello asintotico sono perfettamente uguali. Entrambi tendono a O(n^2).

[thefrog]

Originariamente inviato da mjordan
Non ne avevo mai sentito parlare.

Ti avevo chiesto di quelle formule perchè a livello asintotico sono perfettamente uguali. Entrambi tendono a O(n^2).

in effetti il valore di CQ viene molto simile ma a seconda dei casi potrebbe condurre a percentuali di probabilità diverse....vabbè....vediamo se qualcunaltro ne ha sentito parlare.....

grazie mille

[mjordan]

Originariamente inviato da thefrog
in effetti il valore di CQ viene molto simile ma a seconda dei casi potrebbe condurre a percentuali di probabilità diverse....vabbè....vediamo se qualcunaltro ne ha sentito parlare.....

grazie mille

Percentuali di probabilità... Ma che esame è se non sono indiscreto?

[cionci]

Il chi-quadro è una famiglia di distribuzioni statistiche asimmettriche.
E' la somma del quadrato di N variabili aleatorie continue con distribuzione normale...

[thefrog]

Originariamente inviato da mjordan
Percentuali di probabilità... Ma che esame è se non sono indiscreto?

ma figurati, laboratorio di algoritmi e strutture dati.

PS: per quanto riguarda la macchina...se non avessi furia di venderla perchè pago 8 € al giorno nel parcheggio dell'aci 3000 ce li farei tranquillamente.....fatti un giro sul sito vw golf club per farti un idea del rigirio di pezzi che c'è, giusto stasera, qui su questo forum mi p stato chiesto il cambio + l'asse posteriore....che non costano 100€.......

[thefrog]

Originariamente inviato da cionci
Il chi-quadro è una famiglia di distribuzioni statistiche asimmettriche.
E' la somma del quadrato di N variabili aleatorie continue con distribuzione normale...

l'ho sempre detto io ma nessuno mi da mai retta.....

però mi sai dire qual è la formula da usare???
vado a letto, leggo domattina

grazie cionci.....ma sempre te mi devi risolvere tutto?
mi toccherà mandarti un regalo prima o poi.....

[mjordan]

Originariamente inviato da thefrog
ma figurati, laboratorio di algoritmi e strutture dati.

PS: per quanto riguarda la macchina...se non avessi furia di venderla perchè pago 8 € al giorno nel parcheggio dell'aci 3000 ce li farei tranquillamente.....fatti un giro sul sito vw golf club per farti un idea del rigirio di pezzi che c'è, giusto stasera, qui su questo forum mi p stato chiesto il cambio + l'asse posteriore....che non costano 100€.......

Io lo so perchè ... Hihihihi

[cionci]

http://130.251.121.100/ftparea/Mod7I..._ITeXN.v03.doc

Questa è la formula per distribuzioni normali standardizzate... Mentre ora ti cerco quella per distribuzioni non standardizzate, ma aventi stessa media e varianza...

[thefrog]

Originariamente inviato da cionci
http://130.251.121.100/ftparea/Mod7I..._ITeXN.v03.doc

Questa è la formula per distribuzioni normali standardizzate... Mentre ora ti cerco quella per distribuzioni non standardizzate, ma aventi stessa media e varianza...

non me la fa vedere

[cionci]

http://130.251.121.100/ftparea/Mod7I..._ITeXN.v03.doc

[cionci]

Non mi è riuscito trovare la formula...
Comunque il chi-quadro serve per il famoso test del chi-quadro...

Se cerchi test chi-quadro trovi tanto... Purtroppo le formule non me le ricordo... E' uno dei primi esami che ho fatto...