Algoritmi - Calcolo notazione O-Grande

Ciao a tutti!

Immaginiamo di avere una procedura che viene invocata k volte (k è un valore scelto dall'utente). Lavorando su una matrice di dimensioni m*n, il corpo della procedura prende un tempo pari ad O(m*n) fino ad un attimo prima di valutare l'ultima istruzione.

L'ultima istruzione è allegata al post.

Ecco il significato di ogni parametro:

a = parametro di input, non modificato nel corso dell'esecuzione.
b = parametro di input, non modificato nel corso dell'esecuzione.
c1 = parametro di input, non modificato nel corso dell'esecuzione.
c2 = parametro di input, non modificato nel corso dell'esecuzione.
d = parametro di input, non modificato nel corso dell'esecuzione.
La sommatoria = data una matrice di dimensioni m*n, la sommatoria tiene conto solo delle colonne n-sime per le quali è valida una certa condizione booleana. In particolare, la condizione può essere valida, nel caso migliore, solo sulla prima colonna (quindi la sommatoria è valutata solo una volta), altrimenti, sulla prima colonna più tutte quelle per cui è valida la condizione booleana (tipicamente le ultime 3). Per come è strutturato il programma, la condizione non può mai essere valida su tutte le colonne (quindi la sommatoria non andrà mai da 1 ad n).
elem = numero di elementi della colonna j-sima della matrice per i quali è valida una certa condizione booleana. Il numero preciso di elementi viene calcolato in un tempo pari ad O(m*n).

Tenuto conto di tutto questo, credo che il costo totale sia quadratico (diciamo O(n^2)) dovuto a quell'elem al quadrato nella sommatoria. Visto che la procedura viene eseguita k volte, direi O(k*n^2).

Siete d'accordo?

Grazie in anticipo!

E' solamente O(n^2).

Per grandi valori di n, k diventa insignificante (ed è una costante, quindi dev'essere omessa nella notazione).

Grazie mille per la risposta!
Mi sono appena reso conto di non aver specificato nel primo post che k è un parametro scelto dall'utente, quindi l'intera procedura viene invocata k volte scelte dall'utente. Penso che comunque la complessità resti O(n^2), giusto?

Giusto.

Quando pensi O-grande, pensa sempre alla crescita (per grandi valori di n, quanto veloce è il mio algoritmo?)

Un ottimo libro: amazon.com/Algorithms-Sanjoy-Dasgupta/dp/0073523402/…

Ciao Piero,

mi è stata fatta questa osservazione che mi ha mandato totalmente nel pallone: la complessità è lineare perchè, ok, nella sommatoria c'è quell'elevamento di elem al quadrato ma, alla fine, l'elevamento può essere visto come una moltiplicazione di elem * elem.

Posso solo dirti che: data una matrice di dimensioni m*n, elem è pari al numero di elementi lungo una colonna della matrice che soddisfano una determinata condizione (esempio, su 10 elementi, elem è pari a 3 che, elevato al quadrato, diventa 9).

Qual è il tuo parere? Grazie in anticipo.

Una moltiplicazione (su un computer moderno) è lineare, si, anche se viene elevata al quadrato.

Puoi vedere che se a = 10, oppure a = 1000, fare a*a richiede più o meno lo stesso tempo. Il discorso è diverso se eseguo ad esempio un for loop.

for (1..a)
   for (1..a)
       // codice

In questo caso codice viene eseguito solo 100 volte nel primo caso, ma un milione di volte nel secondo.

Questo:

a*a

Richiede lo stesso tempo, O(1).

Solitamente l'analisi dovrebbe cominciare dal pseudo-codice. Partire dalla formula matematica è... come dire... di poco valore, perchè ci sono diversi modi di implementare la stessa formula. Ad esempio ipotetizziamo di avere un computer che non mi permette di fare moltiplicazioni direttamente sul processore, ma solo di fare addizioni. Allora per implementare la moltiplicazione a*a devo fare:

c = 0
for (1..a)
    c += a

Come vedi tutto ad un tratto questa operazione richiede O(n), non più O(1).

Partendo dalla formula matematica, l'analisi in grande-O è piuttosto vaga e ambigua, perchè devi fare delle asserzioni sull'implementazione e sul computer. Partire dall'algoritmo ha più senso (ed è più utile).