Complessità computazionale del quicksort

[peppesmile]

void scambio(float v[],int i, int j)
{
int tmp;
tmp=v;
v=v[j];
v[j]=tmp;
}

void Qsort(float v[],int inf, int sup)
{
int i=inf,j=sup,pivot=v[(inf+sup)/2];
do{
while(v while(v[j]>pivot)j--;
if(i {
scambio(v,i,j);
i++;
j--;
}
if (i==j)
{
i++;
j--;
}
}while (i<=j);
if(inf if(i }



scusate ragazzi,mi sono inceppato nel calcolo della complessità di questo algoritmo...
devo individuare la relazione di ricorrenza... solo che so per certo che la complessità del quicksort è o(nlog(n)), ma i calcoli non mi tornano.

la base è: tp(0)=0(1)

per calcolare l'induzione bisogna vedere il tempo di calcolo in funzione della dimensione...
secondo i miei calcoli il do while ha tn=o(n) perche' dobbiamo metterci nel caso peggiore ovvero che il pivot sia il l'elemento maggiore del vettore il primo while interno ha complessità o(n) mentre il secondo while o(1) perche se v
tp(n)=n^2+2tp(n/2)

e all'iesima iterazione ottengo

tp(n)= i n^2+2^i tp(n/2)
potreste aiutarmi a capire dove sbaglio???

[dzcosimo]

sbagli completamente la prospettiva
il fatto è che quicksort è un algoritmo che nel peggiore dei casi ha complessità O(n^2), cosa che avviene però staticsamente un numero irrisorio di volte
ha invece complessità O(nlogn) nel caso migliore e medio ovvero quando ogni volta ti si divide l'array esattamente a metà, in questo caso hai
il do while e i due while interni hanno in totale complessità O(n) poichè scorrono l'array in totale una sola volta
la ricorrenza sarà dunque:
T(base): O(1)[esci subito]
T(n): O(n) + t(n/2)
che è la ricorrenza per la complessità O(nlogn)
ti torna?

[peppesmile]

si...grazie mille,non mi ero accorto che nel do while,con i 2 while interni la loro combinazione produce al massimo una solo ciclo completo...

[dzcosimo]

eh si lo so è una delle cose insidiose in quel calcolo