[C/C++] Calcolo complessità algoritmo

[EnergyVortex]

Ciao a tutti, devo calcolare la complessità di tre algoritmi che ci hanno chiesto di implementare però non so bene come calcolarla.
So che un'operazione di assegnamento vale 1 ma già al primo if mi blocco perchè non so che valore dargli.
Vi posto una delle funzioni giusto per farvi un'idea:

void cambia_gravita(struct paziente A[],int N)

{

if (N==0)

{

printf("\nNessun paziente in coda!!\n");

return;

}

int k,G,matr;

G=0;

printf("Inserire la matricola del paziente a cui si vuole cambiare codice gravita:");

scanf("%d",&matr);

for (k=0;k<N;k++)

if (A[k].matricola==matr)

{

while (G<1 || G>4)

{

printf("\n Inserire nuovo codice gravita:");

scanf("%d",&G);

}

A[k].priorita=G*1000+matr;

HeapSort(A);

printf("Codice gravità cambiato \n");

G=0;

return;

}

printf("Numero di matricola non trovato! \n");

return;

}


Ho provato a cercare in rete ma non ho trovato nulla di comprensibile.
Confido in voi.
Ciao e grazie

[goldorak]

Originariamente inviato da EnergyVortex

Ciao a tutti, devo calcolare la complessità di tre algoritmi che ci hanno chiesto di implementare però non so bene come calcolarla.
So che un'operazione di assegnamento vale 1 ma già al primo if mi blocco perchè non so che valore dargli.

Dipende dal modello di calcolo che usi. In genere si assume che il costo (di tempo) di ogni istruzione elementare sia 1 (per l'istruzione di assegnamento).
Per l'if la complessita' e' il massimo tra la complessita' del blocco che viene eseguito se la condizione e' vera e quella del blocco che viene eseguito se la condizione e' falsa.
Per i cicli definiti (while, for,...) il costo e' semplicemente la somma sulle diverse iterazioni del costo delle istruzioni a cui il ciclo si riferisce.

Ad esempio per i cicli in pseudocodice (un esempio semplice semplice):

 for i = 1 to n do
   for j= i to m do
    a[i,j]=0

Che complessita' ha ?

• il ciclo piu' esterno viene eseguito n volte quindi parti con Σ(i=1, n)(costo del blocco indentato).
• il ciclo piu' interno viene eseguito m-i+1 volte quindi parti con Σ(j=i, m)(costo del assegnamento).
• l'assegnamento vale 1 quindi il costo totale e'
• Σ(i=1,n) Σ(j=i,m) (1)
• la sommatoria piu' interna vale m-i+1
• quindi ottieni Σ(i=1,n) (m-i+1)
• semplificando viene m* (Σ(i=1,n) 1) - Σ(i=1,n) i + Σ(i=1,n) 1
• il primo termine e' n*m, il secondo e' -n(n+1)/2 ed il terzo e' n
• quindi la complessita' totale e' nm-n(n+1)/2-n

[EnergyVortex]

Ho fatto come mi hai detto, speriamo bene!
grazie per l'aiuto!