Forum libero

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.

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?
Se invece la moltiplicazione tra A e B è presa in esame, la complessità è O(B), giusto?

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)?