|
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!
Ultima modifica effettuata da MagoAntò il 16/03/2015 alle 16:22 | 
MagoAntò ha allegato un file: Snap1.jpg (24962 bytes)
