[C] Calcolo del costo computazionale dell'insertion sort

[ramy89]

Ho scritto questa funzione per l' insertion sort:

void InsertionSort(int *v, int n)
{
    int i,j;
    for(i=0;i<n;i++)
    {
        j=i+1;
        while(j>0 && v[j]<v[j-1])
        {
            swap(&v[j-1],&v[j]);
            j--;
        }
    }
}

Ho provato a calcolare il costo computazionale.
Che comunque deve essere O(n) nel caso che sia già ordinato, e O(n^2) nel caso sia ordinato in ordine decrescente.
Ho concluso allora che,se n è la dimensione dell' array, il costo è uguale alla sommatoria da 0 a n-1 del costo del while interno.
Nel caso migliore il while interno non parte ma viene efettuato un solo confronto, e qui ci siamo.
Ma nel caso peggiore il while viene eseguito i+1 volte, quindi il costo nel caso peggiore dovrebbe essere la sommatoria che va da 0 a n-1 di i+1, cioè (n^2+n)/2.
Eppure se provo a inserire una variabile globale, che la chiamo contatore, che conta tutte le volte che viene effettuato un confronto (quindi anche se il while non parte viene incrementata di 1), ho un risultato strano.
Mi risulta che il costo è uguale a (n^2+n)/2 se l' array ha dimensione pari , e un costo uguale a (n^2-n)/2 se l' array ha dimensione dispari, ma non riesco a capire perchè
Dovrebbe avere un costo indipendente dal fatto che la dimensione dell' array sia pari o dispari ...

[MacApp]

hm... a naso direi che la "j=i+1" possa farti sforare "v" quando valuti appunto "v[j]" nella condizione d'uscita del "while".

[LeaderGL]

Il calcolo della complessità computazionale è un calcolo valido quando osservato in maniera asintotica.

In tutti e due i risultati finiti che hai osservato il valore trovato facendo tendere n ad infinito è O(n^2).

Ovvero per n -> infinito:
(n^2+n)/2 = (n^2-n)/2 = n^2

quindi tutt'appost. A prescindere dalla validità dei tuoi calcoli o del tuo algoritmo.

[ramy89]

Sforava di un elemento giusto, perchè j=i+1 esce dall' array quando i=n-1, l' ho corretto:

void InsertionSort(int *v, int n)
{
    int i,j;
    for(i=0;i<n-1;i++)
    {
        j=i+1;
        while(j>0 && v[j]<v[j-1])
        {
            swap(&v[j-1],&v[j]);
            j--;
        }
    }
}

Ma ancora non capisco perchè abbia un costo computazionale che dipende dall' avere una dimensione pari o dispari dell' array.Non è che mi basta calcolare l' ordine di grandezza del costo computazione.Voglio capire perchè si comporta così, è una cosa che non so spiegare

[ramy89]

Dopo averlo corretto mi rendo conto che il contatore ha sempre valore (n^2-n), io l' avevo calcolato così:

quindi il costo nel caso peggiore dovrebbe essere la sommatoria che va da 0 a n-1 di i+1, cioè (n^2+n)/2.

Ma la sommatoria in realtà non è da 0 a n-1 , ma da 0 a n-2.
Quindi è la sommatoria da 0 a n-2 di i+1, cioè la sommatoria da 0 a n-2 di i meno la più la sommatoria da 0 a n-2 di 1.
Che fa esattamente (n^2-n)/2.
Probabilmente aveva un costo variabile perchè sforando la dimensione dell' array, andava a leggere un valore nullo o comunque un valore di cui non sapevo il contenuto.
Allora tutto si spiega