|
|
Osserviamo che in generale, un algoritmo ricorsivo, alla i-iterazione, richiama se stesso un numero costante ai di volte su dati di dimensione n-i. Ogni chiamata ricorsiva viene effettuata prima o dopo aver eseguito un numero polinomiale di operazioni. In tal caso la funzione di complessità T(n) dell’algoritmo può essere espressa in termini di:
Generalizzando date a1,a2,…,ah costanti intere non negative, con h costante positiva, si considerano relazioni di ricorrenza nelle quali T(n) dipende da:
Una relazione di questo tipo è della relazione lineare a coefficienti costanti di ordine cotante.
Si ottiene il seguente teorema (delle ricorrenze lineari di ordine costante): siano a1,a2,…,ah costanti intere non negative, con h costante positiva, c>0 e Beta>0 costanti reali, e sia T(n) definita dalla relazione di ricorrenza:
Per dimostrare questo teorema si supponga che ci sia un solo coefficiente j non nullo, ovvero che esista j tale che aj=a mentre tutti gli altri ai sono uguali a zero. Si assuma per semplicità che n = m + kj, per k intero. Sostituendo successivamente si ottiene che:
Si individuano a questo punto due casi possibili:
Analogamente, anche nei casi più generali, ovvero rilasciano le ipotesi iniziali: si dimostra la tesi riconducendo la dimostrazione ai due casi appena risolti. Vediamo per esempio il seguente algoritmo ricorsivo che calcola il minimo elemento di uni insieme n:
Essendo il tempo di calcolo T(n) = T(n-1) + c , allora essendo a = 1 e beta = 0 otteniamo che T(n) è O(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.