Calcolatore nodi albero di ricorsione

Le ricorrenze di tipo divide et impera della forma T di n uguale a volte T di n su b più il lavoro non ricorsivo compaiono in ogni corso di algoritmi quando merge sort, partizioni spaziali binarie o ricorsione multiway vengono disegnati come alberi. Gli studenti hanno bisogno di un conteggio affidabile di quanti nodi stiano a ogni livello e di quanto in profondità cresca l'albero prima che i sottoproblemi raggiungano il caso base. Questo calcolatore di nodi dell'albero di ricorsione accetta il fattore di ramificazione a, il rapporto di riduzione b e la dimensione di ingresso della radice n, percorre l'albero finché la dimensione del sottoproblema è al più uno, e restituisce il conteggio dei livelli, l'altezza, i totali di nodi e foglie, la sequenza di nodi per livello, le dimensioni dei sottoproblemi e due distribuzioni frazionarie del lavoro. Una assume costo unitario per nodo; l'altra assume lavoro proporzionale alla dimensione del sottoproblema, come nel disegno classico del merge sort in cui ogni livello pieno compie ancora lavoro lineare in n.

Cosa conta un albero di ricorsione e come si definiscono i livelli

Un albero di ricorsione è l'immagine di ogni sottoproblema creato da un algoritmo divide et impera il cui tempo soddisfa T di n uguale a volte T di n su b più f di n. La radice rappresenta l'istanza originale di dimensione n. Ogni nodo interno ha esattamente a figli, ciascuno risolve un problema la cui dimensione è quella del genitore divisa per b.

I livelli sono numerati da zero alla radice. Al livello i ci sono a elevato a i nodi, e ciascuno di essi ha dimensione di sottoproblema n divisa per b elevato a i, purché le dimensioni restino reali e positive. La scansione continua finché la dimensione corrente è strettamente maggiore di uno; il primo livello la cui dimensione è minore o uguale a uno viene tenuto come livello foglia dei casi base, poi la scansione si ferma.

Questa convenzione coincide con la condizione di arresto dei manuali nel risolvere direttamente ingressi di dimensione costante. L'altezza dell'albero è il conteggio dei livelli meno uno, il numero di archi su un cammino dalla radice a una foglia. I nodi foglia equivalgono ad a elevato all'altezza quando le dimensioni raggiungono uno su una potenza esatta e, in generale, al conteggio nodi dell'ultimo livello registrato.

I nodi interni sono il totale meno le foglie. Con fattore di ramificazione uno l'albero è una sola spina di lunghezza pari al numero di divisioni successive finché la dimensione è al più uno.

Dove contare i nodi dell'albero aiuta

I corsi di algoritmi e le piattaforme di tutoraggio usano un calcolatore di nodi dell'albero di ricorsione affinché gli apprendisti verifichino profondità e ampiezza per a, b e n arbitrari senza disegnare centinaia di nodi a mano. I generatori di esami necessitano di un oracolo deterministico che segni come errato un preteso conteggio di foglie o di livelli invece di accettare stime asintotiche vaghe.

Gli strumenti di preparazione ai colloqui e i visualizzatori di complessità abbinano gli array per livello a grafici così i candidati vedono perché un divide et impera bilanciato spesso spende lo stesso lavoro a ogni livello quando a è uguale a b. I notebook di ingegneria che prototipano splitter multiway o grafi di task paralleli possono validare il fan-out prima di scrivere scheduler di produzione. La validazione fallita non consuma saldo.