[Algoritmi] Complessità algoritmo

[danix89]

Ho questo pseudo codice del quale devo analizzare la complessità, ma dato che la variabile k (usata per il controllo della condizione del while) ha un andamento irregolare, non riesco a capire quante volte venga eseguito il while.
Qualcuno di buona volontà potrebbe dirmi qual è la complessità di questo algoritmo?

Algoritmo(n)
k ← 0; s ← 0, t ← 0
while k ≤ n do
   for j ← 1 to n do
         s ← j × k
   t ← t + 1
   k ← t + k

[Kaamos]

Originariamente inviato da danix89
Ho questo pseudo codice del quale devo analizzare la complessità, ma dato che la variabile k (usata per il controllo della condizione del while) ha un andamento irregolare, non riesco a capire quante volte venga eseguito il while.
Qualcuno di buona volontà potrebbe dirmi qual è la complessità di questo algoritmo?

Algoritmo(n)
k ← 0; s ← 0, t ← 0
while k ≤ n do
   for j ← 1 to n do
         s ← j × k
   t ← t + 1
   k ← t + k

L'algoritmo è iterativo quindi è sufficiente calcolare quante volte viene eseguita l'operazione dominante, che è quella all'interno del for. Il ciclo interno effettua Θ(n) iterazioni, mentre in quello esterno t e k crescono informalmente così:

t k
0 0
1 1
2 3 = (2+1)
3 6 = (3+2+1)
4 10 = (4+3+2+1)
5 15 = (5+4+3+2+1)
6 21 = (6+5+4+3+2+1) = (6*7)/2

k ogni volta vale la sommatoria di i che va da 1 a t, che vale (t*(t+1))/2. Il while termina quando k vale n (in realtà quando supera n, ma asintoticamente non cambia nulla), cioé quando:

n = k = (t*(t+1))/2

Faccio prima a linkare wolfram che a tentare di scrivere le formule in maniera comprensibile:
http://www.wolframalpha.com/input/?i...+%3D+0+solve+i

La soluzione in funzione di n (quella "positiva", l'unica accettabile in questo contesto) è in Θ(√n), quindi l'algoritmo dovrebbe essere in Θ(n√n).

Però aspetta la conferma (o la smentita) di qualcuno più bravo di me in matematica.

[danix89]

Originariamente inviato da Kaamos
L'algoritmo è iterativo quindi è sufficiente calcolare quante volte viene eseguita l'operazione dominante, che è quella all'interno del for. Il ciclo interno effettua Θ(n) iterazioni, mentre in quello esterno t e k crescono informalmente così:

t k
0 0
1 1
2 3 = (2+1)
3 6 = (3+2+1)
4 10 = (4+3+2+1)
5 15 = (5+4+3+2+1)
6 21 = (6+5+4+3+2+1) = (6*7)/2

k ogni volta vale la sommatoria di i che va da 1 a t, che vale (t*(t+1))/2. Il while termina quando k vale n (in realtà quando supera n, ma asintoticamente non cambia nulla), cioé quando:

n = k = (t*(t+1))/2

Faccio prima a linkare wolfram che a tentare di scrivere le formule in maniera comprensibile:
http://www.wolframalpha.com/input/?i...+%3D+0+solve+i

La soluzione in funzione di n (quella "positiva", l'unica accettabile in questo contesto) è in Θ(√n), quindi l'algoritmo dovrebbe essere in Θ(n√n).

Però aspetta la conferma (o la smentita) di qualcuno più bravo di me in matematica.

In attesa della conferma, ti ringrazio per la risposta chiara Kaamos