[C] Complessità computazionale

[shiony710]

Salve a tutti, avrei bisogno di un aiuto riguardante il calcolo della complessità computazionale, dato che dopo averlo studiato dal libro e da internet non ho comunque capito il modo per calcolarlo, quindi vi chiedo un aiuto utilizzando come esempio un codice che ho creato che devo portare all esame proprio con la sua complessità


#include <stdio.h>

int main()
{
int v[100], n, i, j, position, swap;


printf("Inserisci il numero degli elementi\n");
scanf("%d", &n);

printf("Inserisci %d elementi\n", n);

for ( i = 0 ; i < n ; i++ )
scanf("%d", &v[i]);

for ( i = 0 ; i < ( n - 1 ) ; i++ )
{
position = i;

for ( j = i + 1 ; j < n ; j++ )
{
if ( v[position] < v[j] )
position = j;
}
if ( position != i )
{
swap = v[i];
v[i] = v[position];
v[position] = swap;
}
}

printf("Lista in ordine decrescente:\n");

for ( i = 0 ; i < n ; i++ )
printf("%d\n", v[i]);
int x;
printf("inserisci un intero x \n"); //Setto il valore di x
scanf("%d", &x);
for( i = 0; i < n; i++)
{
if ( v[i] > x)
{
printf("Il primo elemento dell'array=%d e' maggiore di x=%d", v[i], x);
return 0;
}
int somma = 0;
for(i = 0; i < n; i++)
{
somma += v[i];
if (somma > x)
{
printf("Vengono sommati gli elementi del vettore fino al v[%d],\nLa loro somma e' %d maggiore di x %d. ", i, somma, x);
return 0;
}
}


printf("La somma di tutti gli elementi dell'array e' minore di x= %d\n",x);
}
return 0;

}

[wingman87]

Questo è il codice che hai scritto nell'altro thread?
E' ancora sbagliato: come ti dicevo dovresti dividere il codice in funzioni, sia per renderlo più leggibile sia perché la richiesta iniziale era di scrivere una funzione che restituisse la sequenza di elementi, non è sufficiente "rilevare" che esiste e stamparne la somma.

Detto questo, la complessità non si spiega in due righe, diciamo che in generale si possono dire un paio di cose, per capirne di più poi dovresti essere più specifico nelle tue domande:
- la complessità si esprime in relazione all'input dell'algoritmo
- la complessità può essere spaziale, cioè quanta memoria viene dedicata ai dati di supporto dell'algoritmo, o temporale, cioè quanto tempo impiega l'algoritmo a restituire l'output
- per calcolare la complessità di un algoritmo si segue il ragionamento che vi è alla base, in relazione a un input "generico" (caso medio). Può essere interessante anche calcolare la complessità del caso migliore con un input apposito che l'algoritmo risolve in un tempo minimo. Ad esempio se in input all'insertion sort dai un vettore già ordinato, esso ci impiegherà solo n passi, dove n è la dimensione del vettore di input. Il selection sort invece ci impiegherà sempre n^2 passi. D'altra parte anche il caso peggiore può essere interessante, sempre nel caso dell'insertion sort il caso peggiore è quando il vettore è ordinato al rovescio perché è necessario un numero maggiore di swap degli elementi, invece per il selection sort non cambia nulla perché il numero di swap è sempre n.

[shiony710]

Ora provvedo a sistemare il codice, comunque la mia richiesta riguarda la complessità riguardante il tempo ed il caso peggiore, dato che sono quelle che mi chiederanno. Vorrei sapere se è giusto dire che quest'algoritmo ha complessità O(n^2), e che è giusto dire che generalmente il selection sort ha per complessità O(n^2).

[wingman87]

Se io fossi il professore ti chiederei perché ha complessità O(n^2) ed è lì che si capisce se hai capito come si calcola la complessità.
Inoltre se l'avessi scomposto in funzioni ti chiederei qual è la complessità delle singole funzioni.
Posso anche dirti di sì, che è corretto quello che dici, ma credo che ci farai poco all'esame.
Tra l'altro la seconda parte del tuo programma (che dovrebbe diventare una funzione) secondo te che complessità ha nel caso migliore? E nel peggiore? Si può fare di meglio, ragionaci su.

[shiony710]

La complessità è O(n^2), perché ci sono doppi cicli annidati se non sbaglio, comunque se non sbaglio la prima parte cioè quella dell'ordinamento dovrebbe essere O(n^2), mentre quello del confronto dovrebbe essere O(n).


P.S. Comunque infatti non voglio che mi dici solo se è giusto o sbagliato, perché so che non concluderei niente, a me interessa capire quindi ti ringrazio per l'aiuto che mi stai dando