Tempo esecuzione algoritmo

[matteo1095]

Qualcuno può aiutarmi a scrivere l'equazione di ricorrenza di questo algoritmo io non riesco a capire le chiamate ricorsive come separano l'array..grazie in anticipo

[ienaplinsky]

Se non erro dovrebbe essere:

T(n) = c se n <= 1
T(n) = T(n/3) + T((2n/3) + 1) + 0(N)

se n <= 1 l'algoritmo ha costo c costante, se è maggiore di 1, copia a in b che ha costo n ad ogni chiamatq, poi fai altre 2 chiamate ricorsive una con input ridotto a 1/3, l'altra con input ridotto a 2/3 + 1.

[matteo1095]

ciao ienaplinsky il fatto che alle chiamate ricorsive somma inizio+n/3 e alla seconda inizio+2n/3 è ininfluente?

[ienaplinsky]

Si è ininfluente al primo giro l input viene diviso in n / 3 e 2 n + 1 l input di destra viene diviso nello stesso modo, come anche l' input di sinistra e chiamata dopo chiamata fino a che n < = 1

[ienaplinsky]

Scusa mi sono accorto che ho detto una baggianata, non è cosi banale ora che mi ci fai pensare. Cerco di fare due conti. scusami.

[matteo1095]

Okok grazie ienaplinsky che mi stai aiutando aspetto tue notizie