[Algoritmi] Albero di ricorrenza

[daffeen]

Ciao a tutti, ho il seguente dubbio, vi ringrazio in anticipo:
Immaginiamo di avere un albero di ricorrenza in cui ogni nodo interno ha cardinalità 1 (quindi può essere visto come una lista).
Ogni nodo ha complessità \(\displaystyle \Theta(n) \) riceve in ingresso la dimensione che riceve in ingresso il padre - 1. La radice riceve in ingresso \(\displaystyle n \).
Quindi sostanzialmente possiamo vedere il tutto come una lista
\(\displaystyle n \ ; \ n-1 \ ; \ n-2 \ ; \ ... \ ; \ 1 \)
dove quest' etichetta è la dimensione che riceve quel nodo a quel livello.

Ora, il livello 0 (quello della radice) riceve dimensione n, il suo costo per risolvere il problema è \(\displaystyle \Theta(n) \), quindi a quel livello il costo è \(\displaystyle \Theta(n) \).

Il livello 1 riceve dimensione \(\displaystyle n-1 \) che è comunque un \(\displaystyle \Theta(n) \), quindi quel livello costa \(\displaystyle \Theta(n) \).
e così via, tranne l'ultimo nodo (che riceve dimensione 1) costa \(\displaystyle \Theta(1) \).

Il costo totale è \(\displaystyle n-1 \) [lunghezza albero - l'ultimo] * \(\displaystyle \Theta(n) \) = \(\displaystyle \Theta(n^2) \).
Ma allora perché il penultimo livello che riceve dimensione 2, non è \(\displaystyle \Theta(1) \) bensì \(\displaystyle \Theta(n) \)?
E perché il padre di questo che riceve dimensione 3 non è anch'esso theta(1)? E così via fino a salire. In questo caso il costo per risolvere l'intero problema sarebbe n*\(\displaystyle \Theta(1) \) = \(\displaystyle \Theta(n) \)

Quello che penso è che mi sembra arbitrario il modo in cui indico cosa quel livello riceve in ingresso. Se riceve in ingresso una costante, allora è \(\displaystyle \Theta(1) \), se riceve in ingresso \(\displaystyle n-x \) allora costa \(\displaystyle \Theta(n) \).

Spero di essermi spiegato bene, grazie.

[apatriarca]

Per poter dire che un nodo ci impiega tempo costante è necessario imporre la costante A PRIORI. Un algoritmo è della forma \(n \, \Theta(1) \) solo se esiste una singola costante che vale per TUTTI i nodi decisa INDIPENDENTEMENTE da \(n\). Nel tuo caso non è certamente così. Scelta una costante, per esempio \(5\) puoi sempre prendere un input (per esempio \(100\)) per cui un numero di nodi proporzionale a \(n\) ha costo proporzionale a \(n\) e maggiore della costante scelta.