Newsgroup: it.comp.lang.c
Titolo: complessità asintotica O

Salve a tutti
Io so per definizione che f(n) č O(g(n)), cioč f(n) = O(g(n)) se e soltanto
se esistono due costanti positive c e n0 tali che f(n)<=c * g(n), per tutti
i valori di n >= n0, con c > 0. Il punto č: n0 deve essere calcolato
provando di volta in volta se la disugliaglianza č verificata, ma c ? c come
viene calcolato? C'č una regola fissa? Finora ognuno mi ha dato un parere
diverso, ho le idee abbastanza confuse  e tra l'altro questi metodi non
vanno bene per tutti i tipi di disuglianze viste..
Vi prego aiutatemi ho l'esame solo tra 10 giorni :°(
Disperato

 vanno bene per tutti i tipi di disuglianze viste..
Hai un approccio sbagliato. Le costanti n0 e C servono solo per staccare la 
disuguaglianza dai fattori costanti, che potrebbero alterarne per alcuni 
valori la veridicita'.
Nella pratica non ti servono a nulla per il calcolo della complessita', ma 
ti servono per dimostrare che la complessita' calcolata e' matematicamente 
corretta.
In realta' l'analisi e' piu' fine.
Il valore di n0 dovresti considerarlo in alcuni casi, per decidere qual'e' 
la soglia al di sotto del quale un algoritmo con un costo asintotico basso 
ma un alto costo di startup e' preferibile ad uno con una complessita' 
asintotica piu' alta, ma un basso costo di startup.
Ad esempio per cercare su stringhe di lunghezza 20 o 30 non ha sento usare 
una KMP... ti costa di piu' l'inizializzazione.
La costante C si usa in genere per confrontare algoritmi con la stessa 
complessita' asintotica.
-- 
Mox
"Trust the programmer."
"Don't prevent the programmer from doing what needs to be done."
"Keep the language small and simple."
"Provide only one way to do an operation."

non č che ho capito bene.. potresti farmi qlc esempio o postarmi qlc buon
link? Ti ringrazio
Paolo

 link? Ti ringrazio
Il calcolo della complessita', a meno che non si parli di algoritmi 
ricorsivi nel qual caso diventa non molto intuitiva la gestione delle 
equazioni di ricorsione, si fa' in genere in modo semplice senza molte 
complicazioni matematiche.
A meno che non ti interessi calcolare anche la costante C, in qual caso il 
calcolo si complica e diventa noioso e lungo. Non che ti serva poi molto, 
visto che la costante dipente (nella pratica) molto da come scrivi il 
programma, piu' che dall'algoritmo in se (o meglio, l'implementazione puo' 
stravolgere parecchio questa costante).
Tutto il formalismo che si introduce serve per rendere il tutto coerente 
livello matematico (in particolare per la definizione di asintotico, 
ammesso che sia il termine corretto).
Capire a cosa servono la C e n0 non ti insegna di certo a calcolare la 
complessita', ti serve solo per capire come mai quello che calcoli ha senso 
sempre.
Per il resto, ci sono vari gruppi che parlano solo di informatica, in tutti 
i suoi aspetti, in cui sapranno senz'altro spiegarti quello che ho detto io 
in termini che ti siano piu' comprensibili.


ti ringrazio! Avevo capito che il calcolo di c e n0 alla fine mi dimostra
solo la correttezza che un algoritmo è di una certa complessità, e so che
nella pratica ciò non mi serve a molto, ma putrppo è proprio quello che
daranno nella prova... Ti ringrazio lo stesso , magari darò un'occhiata a
qlc altro ng
Ciao Paolo