Tutto e di + - O grande?

Forum - Tutto e di + - O grande?

hackersitiz (Normal User)
Pro

Messaggi: 120
Iscritto: 29/09/2010

Postato alle 12:13
Sabato, 13/11/2010

Ciao a tutti(di nuovo io,voi direte noooo!)
Ho avuto qualche problema con il computer e robe varie..
Facendo esercizi in C soprattutto i fibonacci o il fattoriale ho visto delle formule con la O davanti??
a che serve?
Ad esempio O(2^n)...
potreste darmi una spiegazione semplice?

HeDo (Founder Member)
Guru^2

Messaggi: 2765
Iscritto: 21/09/2007

Postato alle 13:00
Sabato, 13/11/2010

Testo quotato

Postato originariamente da hackersitiz:

Ciao a tutti(di nuovo io,voi direte noooo!)
Ho avuto qualche problema con il computer e robe varie..
Facendo esercizi in C soprattutto i fibonacci o il fattoriale ho visto delle formule con la O davanti??
a che serve?
Ad esempio O(2^n)...
potreste darmi una spiegazione semplice?

rimanendo al livello dell'omino della panchina ti posso dire che O(qualcosa) vuol dire che il grado di complessità della funzione/algoritmo/procedura è, in un caso asintotico, pari a "quello che c'è dentro la parentesi"

se un algoritmo è O(2^n), presupponendo che "n" sia il numero dei dati di input, esso eseguirà 2^n "passi", quindi scala esponenzialmente.

spero di aver reso l'idea. Ovviamente è sempre meglio che un algoritmo abbia una complessità lineare o polinomiale O(n^k), con k l'esponente (fisso), in quanto la complessità esponenziale rende il problema intrattabile anche con un set di input relativamente contenuto.