Forum libero

- Scritto da:
> Non pretendo che mi si faccia un corso sul forum,
> ma voglio solo chiarirmi le
> idee.
>
> da questo sito
> http://digilander.libero.it/unno2/sort/complessita
> ho trovato che
>
> Dato un algoritmo A la complessità viene
> determinata contando il numero di operazioni
> aritmetiche e logiche, accesso ai file, letture e
> scritture in memoria, etc.
>
>
> Occorre tener presente che il tempo t dipende dai
> seguenti fattori:
>
> la macchina usata, intendendo con ciò l'hardware,
> il sistema operativo, il compilatore ed, in
> macchine multitasking, il
> carico;
> la configurazione dei dati in ingresso;
> la dimensione dei dati in ingresso.
>
> il ché significa, come dico io, che la
> complessità computazionale di un algoritmo
> dipende anche dalla macchina presa in
> considerazione per la sua
> esecuzione.


La complessità computazionale non dipende da fattori tecnici come il processore, i tempi delle istruzioni assembly etc. etc.
La complessità computazione è misurata come numero di operazioni necessarie in funzione della grandezza dei dati in ingresso.
Cosa si intende per operazione o dimensione dei dati in ingresso lo devi decidere tu in base alla tue necessità.
Es: se devi ordinare dei dati, la dimensione del problema potrebbe essere il numero degli elementi da ordinare.

>
> Quindi, supponendo di possedere una macchina che
> non sa eseguire moltiplicazioni ma solo
> addizioni...
>
> se l'addizione tra A e B è O(1) (vera per
> ipotesi, per le peculiarità della macchina
> astratta presa in
> considerazione)
>
> B addizioni sono O(B), giusto?

Giusto

> Se invece la moltiplicazione tra A e B è presa in
> esame, la complessità è O(B),
> giusto?

No. Dipende dall'algoritmo che usi per fare la moltiplicazione.
Pensa alla regola della moltiplicazione come la si faceva alle elementari.
Dati due numeri A e B servono tante somme quante sono le cifre di B meno uno. Per produrre le somme parziali l'algoritmo consulta una tabella contente le tabelline.

Con questo metodo se come dimensione del problema consideri il modulo dei numeri l'operazione risulta logaritmica O(logN)

Es: se B è 1000, allora log(1000) = 3, quindi servono 3 somme
se B = 100000, log(10000) = 5, quindi servono 5 somme.

Come vedi il numero di somme è il logaritmo della dimensione del problema.



Se invece come dimensione del problema consideri il numero di cifre dei fattori della moltiplicazione, allora la complessità risulta lineare O(N)




>
> Quindi, tornando al caso in esame, ovvero
> sommatoria di N
> numeri:
> con ciclo: O(N)
> con formula di gauss: O(N).
>
>
> QED.
>
>
> Ps per avvelentani: come fa ad essere la
> moltiplicazione polilogaritmica in una macchina
> dove le addizioni sono
> O(1)?

Come descritto sopra. Non sono avvelentani però spero di essermi spiegato