Complessità e costo di un algoritmo

[John360]

sto sentendo spesso parlare di complessità o di costo di un algoritmo, ma non ho capito bene cos'è e come si fa a calcolare dato che ho visto che qualcuno in base ad un certo algoritmo qualche volta ne dichiarava anche la complessità.
Sapreste spiegarmi? grazie!

[Kaamos]

Originariamente inviato da John360
sto sentendo spesso parlare di complessità o di costo di un algoritmo, ma non ho capito bene cos'è e come si fa a calcolare dato che ho visto che qualcuno in base ad un certo algoritmo qualche volta ne dichiarava anche la complessità.
Sapreste spiegarmi? grazie!

La teoria della complessità è una bella branchia dell'informatica che non si può liquidare in un post, prima leggi qualcosa e poi fai domande specifiche, sul web c'è molto materiale, basta aprire Google...

Principalmente è la parte dell'informatica che si occupa di stimare la durata dell'esecuzione di un algoritmo (in funzione dell'input) e lo spazio necessario in memoria.

[John360]

sisi ho gia letto su wikipedia e in generale ho capito a cosa si riferisce però non ho capito nello specifico, ad esempio se io scrivessi un algoritmo che ordina un array, come faccio a capirne la complessità? e poi: complessità e costo sono 2 cose differenti?

[Kaamos]

Originariamente inviato da John360
sisi ho gia letto su wikipedia e in generale ho capito a cosa si riferisce però non ho capito nello specifico, ad esempio se io scrivessi un algoritmo che ordina un array, come faccio a capirne la complessità? e poi: complessità e costo sono 2 cose differenti?

La complessità temporale di un algoritmo di ordinamento ovviamente dipende dall'algoritmo in questione: il COME è una cosa non banale, che all'università si studia in lezioni su lezioni solo per iniziare a familiarizzarci...
Se non è un algoritmo ricorsivo il modo più semplice (uno dei primi che si affronta all'inizio dei corsi universitari che trattano la complessità) è trovare l'operazione dominante, cioé quella che viene svolta più volte, è capire quante volte viene effettuata in funzione dell'input. Ovviamente se l'istruzione non ha costo costante il numero di volte va moltiplicato per il costo dell'istruzione stessa.

Si di solito si usano come sinonimi.

Ripeto, è impensabile affrontare l'argomento su un forum. On-line trovi le dispense delle varie università se t'interessa l'argomento...

[John360]

ok allora aspetterò di studiarlo all'università però prima mi potreste fare un esempio? tipo: la complessità di un algoritmo bubble sort per ordinare un array è .... perchè ....
sempre se non è troppo complesso da spiegare, senno grazie lo stesso

[Kaamos]

Originariamente inviato da John360
ok allora aspetterò di studiarlo all'università però prima mi potreste fare un esempio? tipo: la complessità di un algoritmo bubble sort per ordinare un array è .... perchè ....
sempre se non è troppo complesso da spiegare, senno grazie lo stesso

Non ho detto di aspettare l'università eh, ben venga l'interesse personale, dico solo di approfondire prima per bene le numerose dispense disponibili on-line.

Questo è un codice trovato on-line:

public static void bubbleSort1(int[] x) {
    int n = x.length;
    for (int pass=1; pass < n; pass++) {  // count how many times
        // This next loop becomes shorter and shorter
        for (int i=0; i < n-pass; i++) {
            if (x[i] > x[i+1]) {
                // exchange elements
                int temp = x[i];  x[i] = x[i+1];  x[i+1] = temp;
            }
        }
    }
}

L'operazione che viene eseguita più volte nel caso peggiore è la verifica della condizione del for interno: oprazione del genere sono assunte come dal costo costante. E' dentro ad un ciclo che itera un numero di volte dipendente dalla dimensione dell'input (n), quindi viene eseguito CIRCA n volte. A sua volte questo ciclo è annidato in un altro ciclo che viene eseguito pure lui unnumero di volte dipendente da n. A questo punto, l'iterazione esterna viene eseguita per circa n volte, ed ad ogni volta c'è un ciclo che fa circa n iterazioni... quindi l'operazione dominante è eseguita circa n*n volte, cioé n^2.

E' fondamentale capire che ciò che importa è l'ordine di grandezza della complessità, non una complessità precisa... un algoritmo che ci mette 100*n viene considerato come un algoritmo che fa n passi, perché sono entrambi linear: ciò che interessa è come cresce la complessità temporale in funzione dell'input, se in modo lineare, quadratico, cubico, fattoriale, logaritmico, costante...

Un altro aspetto fondamentale è il passaggio dei parametri, che in Java avviene in un modo un po' particolare ma in C/C++ assume un ruolo talvolta fondamentale in questo calcolo, per assurdo può anche superare il costo dell'algoritmo stesso.

Oh, prendi con le pinze tutto quel che ti dico, viene dalla tastiera di un appassionato che studia informatica al primo anno, niente di più...

P.S.: per altro la sezione è sbagliata, andava nella stanza Programmazione.

[John360]

beh pure io sono un appassionato che studia informatica al primo anno però tutte ste cose non le so XD in ogni caso grazie, ho capito meglio l'argomento.
Un'ultima domanda, come mai quando si descrive la complessità di un algoritmo si scrive ad esempio "omega" o altre lettere? che significano?

[Kaamos]

Originariamente inviato da John360
beh pure io sono un appassionato che studia informatica al primo anno però tutte ste cose non le so XD in ogni caso grazie, ho capito meglio l'argomento.
Un'ultima domanda, come mai quando si descrive la complessità di un algoritmo si scrive ad esempio "omega" o altre lettere? che significano?

Con la O grande si indica il caso peggiore, con la Omega il caso migliore

Comunque se studi informatica la farete sicuramente.