Equazione di costo e complessità algoritmo

di
Lorenzo Norcini
il
3 risposte
L
Lorenzo Norcini
Pochi posts
Iscritto da
gen, 2014
Messaggi:
2

Equazione di costo e complessità algoritmo

Ciao a tutti!
Sono al primo anno della facoltà di ingegneria informatica e per l'esame orale mi è stato richiesto un codice in C con tanto di equazione di costo e complessità algoritmo.
Ora, il codice l'ho scritto e mi sembra andare bene solo che non ho la più pallida idea di come si ricavi l'equazione e la complessità
Potete aiutarmi? magari spiegandomi anche il procedimento.
Allego qui la funzione: 

int del_post_thres (struct list **ptrptr , int thres){
    int count = 0;
    struct list * tmp , * free_;
    while (*ptrptr != NULL && (*ptrptr)->value+1 <= thres){
        (*ptrptr)->value += 1;
        ptrptr = &(*ptrptr)->next_ptr;
    }
    tmp = *ptrptr;
    *ptrptr = NULL;
    while ( tmp != NULL){
        free_ = tmp;
        tmp = tmp->next_ptr;
        free(free_);
        count++;
    }
    free(tmp);
    return count;
}

Grazie a tutti in anticipo.

3 Risposte

  • shodan
    shodan
    Molto attivo
    Iscritto da
    apr, 2010
    Messaggi:
    744

    Re: Equazione di costo e complessità algoritmo

    Per quanto riguarda il costo, commenti e dichiarazioni di variabili hanno costo c0, i confronti hanno costo c1, l'assegnazione di un valore/variabile a una specifica variabile ha costo c1 moltiplicato il numero di assegnazioni su detta variabile.
    Ad es. 
    
int count = 0; // costo c1. La variabile è dichiarata e inizializzata allo stesso tempo.
...

(*ptrptr)->value += 1; // costo potenziale c1, ma dato che si trova all'interno 
                                     di un ciclo while, il suo costo varia da c0 (il ciclo while 
                                     non è eseguito) a cN (dove N è il numero di nodi che soddisfano
                                     condizione del while).

tmp = *ptrptr; // costo c1
...

free_ = tmp; // come (*ptrptr)->value += 1;
    Raggruppi i termini con lo stesso costo, li moltiplichi per il numero di ripetizioni e ottieni l'equazione di costo.

    Per quanto riguarda la complessita, basta verificare le peggiore condizioni di uscita dei cicli.
    Nei casi peggiore devi scorrere tutta la lista, quindi la complessità e O(N) per entrambi i cicli.
  • L
    Lorenzo Norcini
    Pochi posts
    Iscritto da
    gen, 2014
    Messaggi:
    2

    Re: Equazione di costo e complessità algoritmo

    Grazie mille della risposta che mi ha già chiarito diverse cose!
    Allora vediamo se ho capito....
    L' equazione di costo sarebbe quindi la somma di tutti i vari costi moltiplicati per il numero di volte che si ripetono:
    Costo(N) = c1 + c0 + c0 + (c1 + c1)N + c1 + c1 + ( c1 + c1 + c1 + Free)N + Free + Return.
    Avrei alcune domande:
    - Negli costi di alcuni degli algoritmi del mio libro (Ad es Bubblesort ) ignora sostanzialmente tutto ciò che si trova al di fuori dei cicli. Lo fa in quanto sono trascurabili su liste di lunghe dimensioni?
    - Nella funzione che ho scritto se ci troviamo nel peggior caso abbiamo raggiunto la fine della lista nel primo while e pertanto non si entra nemmeno nel secondo, hanno comunque entrambe N come caso peggiore?
    - Il Free e il return hanno un costo? Quale?
  • shodan
    shodan
    Molto attivo
    Iscritto da
    apr, 2010
    Messaggi:
    744

    Re: Equazione di costo e complessità algoritmo

    Lorenzo Norcini ha scritto:

    Grazie mille della risposta che mi ha già chiarito diverse cose!
    L' equazione di costo sarebbe quindi la somma di tutti i vari costi moltiplicati per il numero di volte che si ripetono:
    Costo(N) = c1 + c0 + c0 + (c1 + c1)N + c1 + c1 + ( c1 + c1 + c1 + Free)N + Free + Return.
    Si, a parte c0 che puoi omettere dato che il costo è 0.
    - Negli costi di alcuni degli algoritmi del mio libro (Ad es Bubblesort ) ignora sostanzialmente tutto ciò che si trova al di fuori dei cicli. Lo fa in quanto sono trascurabili su liste di lunghe dimensioni?
    Si. Se il costo interno ai cicli è, diciamo, 1000 a causa di quanti elementi processi, il costo esterno diventa trascurabile. Se mandi al limite N ->infinito, N^2 + K, k sparisce.

    - Nella funzione che ho scritto se ci troviamo nel peggior caso abbiamo raggiunto la fine della lista nel primo while e pertanto non si entra nemmeno nel secondo, hanno comunque entrambe N come caso peggiore?
    La complessità, a differenza del costo, è fissa e dipende unicamente (in questo caso) dal ciclo e dal numero di elementi che processa. Poco importa che il ciclo sia eseguito o no. Per questo si parla di O(N).
    - Il Free e il return hanno un costo? Quale?
    Entrambi hanno costo c1, ma mentre la free() si comporta come le variabili, cioè dipende da quante volte la invochi, il return termina la funzione per cui in caso di vari return sparsi in un funzione, il costo della stessa varia (tuttavia non cambia il modo di calcolo complessivo, al massimo si azzerano alcuni parametri).
Devi accedere o registrarti per scrivere nel forum
3 risposte