|
|
Esistono particolari relazioni di ricorrenza lineari caratterizzate dal fatto che esse partizionano i dati in maniera bilanciata. Ovvero, il problema iniziale di dimensione n, viene suddiviso in a sottoproblemi di dimensione n/b. Se si dividono i dati e si ricombinano i risultati in tempo polinomiale, la funzione di complessità T(n) può essere espressa in termini di:
Si ottiene il seguente teorema (delle ricorrenze lineari con partizione bilanciata): Siano a,b costanti intere tali che a >=1 e b >= 2, c > 0 , d >= 0 e Beta >= 0 costanti reali. Sia T(n) data dalla seguente relazione:
La dimostrazione è analoga a quella del teorema delle ricorrenze lineari di ordine costante. In questo caso però l' ipotesi è che n sia una potenza di b, n = bk. Per sostituzioni successive, otteniamo una determinata relazione. A questo punto si analizzano i 3 casi possibili, ottenendo varie e diverse semplificazioni. Per esempio per l' algoritmo ricorsivo della ricerca binaria, vale che T(n) <= T(n/2) + c. Poiché a = 1 e b = 2 ed essendo:
ne segue che T(n) è O(log n).
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.