Calcolo della complessità di un algoritmo

[terminal1]

Ciao a tutti,
vorrei calcolare la complessità di un algoritmo:
in esso ci sono:

assegnamenti

if

for

la costruzoiine di una spline cubica

la trasposta di un vettore

Ho letto che la complessità nel caso pessimo, consiste nel calcolare la complessità dell'algoritmo quando vengono esplorati tutti i "rami".
Nel mio algoritmo i rami vengono sempre esplorati tutti... come assegno il costo ad ogni tipo di istruzione?
Quali sono i costi?
Grazie

[_tenebra]

per gli assegnamenti in generale viene considerato un tempo costante (1). L'if è composto da un ramo then e un ramo else, quindi verrà eseguito per forza uno solo dei due. Va considerato il ramo computazionalmente più pesante. Poi, per quanto riguarda il for, bisogna sapere se il numero di iterazioni è dipendente o meno dall'input dell'algoritmo. La costruzione della spline cubica non ricordo quale complessità abbia, mentre la trasposizione di un vettore dovrebbe avere complessità n, con n dimensione del vettore stesso.

[apatriarca]

Che cosa intendi con "costruzione di una spline cubica"? La valutazione del suo valore in un punto? In tanti punti? La risoluzione di un qualche sistema (lineare o no) al fine di trovare i parametri della curva che soddisfino determinati vincoli?

Che cosa intendi con "rami" nel tuo particolare algoritmo? Che cosa significa che vengono esplorati tutti?

[terminal1]

"tenebra":per gli assegnamenti in generale viene considerato un tempo costante (1). L'if è composto da un ramo then e un ramo else, quindi verrà eseguito per forza uno solo dei due. Va considerato il ramo computazionalmente più pesante. Poi, per quanto riguarda il for, bisogna sapere se il numero di iterazioni è dipendente o meno dall'input dell'algoritmo. La costruzione della spline cubica non ricordo quale complessità abbia, mentre la trasposizione di un vettore dovrebbe avere complessità n, con n dimensione del vettore stesso.

Io ho utilizzo due if solo per verificare la correttezza dei dati in input, cioè i rami dell'if stampano a video un messaggio; quindi, dovendo verificare che tutti gli elementi soddisfino o meno una condizione, la complessità di ciascun if dovrebbe essere O(n) ?

Per il for, il numero di iterazioni dipende da tutti gli n valori dati in input.. anche se non "direttamente" perchè nel for scorro una matrice che ho costruito dagli n elementi iniziali...

"apatriarca":Che cosa intendi con "costruzione di una spline cubica"? La valutazione del suo valore in un punto? In tanti punti? La risoluzione di un qualche sistema (lineare o no) al fine di trovare i parametri della curva che soddisfino determinati vincoli?

Che cosa intendi con "rami" nel tuo particolare algoritmo? Che cosa significa che vengono esplorati tutti?

Per quanto riguarda la costruzione della spline cubica, effettuo (in ambiente MATLAB) una interpolazione degli n elementi in input tramite un comando e quindi non conosco effettivamente che tipo di istruzioni esegua...

Con "vengono esplorati tutti" intendevo che, tolti gli if , vengono attraversati tutti i rami dei for (gli altri sono o assegnamenti, o "selezioni" di elementi di un vettore/matrice).


Comunque, per rendere l'idea, posto una semplificazione dell'algoritmo:

x = [1 2 3 ..]
y = [1 2 3 ... ]

if x non_contiene_doppioni
print ("ok")
else print ("errore")

if dimensioni_x = dimensioni_y
print ("ok")
else print ("errore")

pp = spline ( x, y ) %% costruisco la spline

[a, b, c, d] = estraiDatiDa (pp) %% estarggo delle informazioni dalla variabile pp e le memorizzo nelle variabili a,b,c,d..

c'= derivataDI (C) %% calcolo la derivata della variabile c (sottoforma di matrice)

c'Val= valutaPolinomi (c', intervallo) % valuto polinomii in un intervallo definito (i coefficienti sono gli elementi di ogni riga della matrice c')

radici_c'= radici(c') % calcolo con il FOR le radici dei polinomi di tutta la matrice; utilizzo il for per scorrere tutti gli elementi

trasp_c'=trasposta(c') % calcolo la trasposta

[terminal1]

up

[apatriarca]

La complessità di non_contiene_doppioni può anche essere quadratica a seconda di come sia stato effettuato il test (è almeno lineare). spline risolve un sistema tridiagonale e quindi la sua complessità sarà tra il quadratico e il cubico (non ho idea di quale algoritmo utilizzi e neanche se esistono algoritmi efficienti per questo caso). estraiDatiDa non ho idea di che complessità abbia. derivataDI e valutaPolinomi immagino abbiano complessità lineare. radici non ho capito che cosa faccia esattamente. trasposta è lineare. In generale non è possibile fare discorsi molto precisi su di una semplificazione del genere. Conoscendo però meglio che cosa si fa ad ogni passaggio non dovrebbe però essere difficile calcolare tale complessità. In cosa incontri esattamente difficoltà?

[terminal1]

Grazie per tutti i suggerimenti e i consigli; ho reperito un buon libro di Algoritmi...
Mi studio un pò quello che interessa e poi, se qualcosa non fosse chiaro, torno a chiedervi aiuto
Per ora grazie a tutti