Big-O per alberi immutabili

Question

Big-O per alberi immutabili

#1 da (4 voti)

3

Come calcoli la complessità di tempo e spazio per un algoritmo ad albero che crea una copia di un albero, ma riutilizza il più possibile l'albero originale?

Ad esempio,

   A
  /|\
 B C G
  /|\
 D E F

Per cambiare E, possiamo adottare un approccio più efficiente, piuttosto che copiare l'intero albero:

Copia E e modifica il valore, chiama questo E '
Copia C e puntalo su E 'invece di E, chiama questo C'
Copia A e punta a C ', chiama A'

Il nuovo albero ha questo aspetto.

   A'
  /|\
 B C'G
  /|\
 D E'F

Il tempo impiegato per gli aggiornamenti dipende completamente dal valore che si desidera modificare e dal numero di nodi padre tra esso e la radice, anziché il numero totale di elementi.

Nel peggiore dei casi, per aggiornare un nodo, devi modificare h elementi, dove h è l'altezza (profondità massima) dell'albero. È corretto esprimere la complessità come O(h) (piuttosto che in termini di n )?

In caso affermativo, quale sarebbe un modo sensato per tracciare questo grafico su un grafico che utilizzava l'asse y per n e l'asse x per Big O? Includere un asse secondario y come h ? Come dimostreresti che h è probabilmente molto più piccolo di n ?

immutability big-o trees update

posta Dan Prince 04.09.2015 - 22:09

fonte

1 risposta

Leggi altre domande sui tag immutability big-o trees update

Come tenere traccia delle attività tecniche con BDD? Modifica efficiente dei file di testo [duplicato]

score 4 · Accepted Answer

Is it sane to express the complexity as O(h) (rather than in terms of n)?

Assolutamente. È comune e utile indicare il big-O di un algoritmo in termini di più variabili.

How would you show that h is likely to be far smaller than n?

Dipende dalle proprietà dell'albero che non hai specificato. cratchet freak ha correttamente affermato che per gli alberi equilibrati h è un logaritmo di n, che è anche la risposta più utile che posso dare, quindi cercherò di fornire la giustificazione per tale affermazione.

Lascia che n sia il numero di nodi nell'albero e a sia l'arità dell'albero (cioè se ogni nodo ha al massimo 2 figli, ciò significa che a è 2). Un albero di altezza 1 può avere solo 1 nodo e 1 < %codice%. Un albero di altezza 2 può avere fino a 1 + un ¹ nodi, poiché il 1 nodo all'altezza 1 può avere fino a a figli, e 1 + a < un ². Un albero di altezza 3 può avere fino a 1 + a ¹ + a ² nodi, poiché ciascuno dei nodi a livello 2 può avere fino a a bambini ciascuno e 1 + a ¹ + a ² < un ³. Dovrebbe essere chiaro che per un albero arioso di altezza h, il numero massimo di nodi a è tra un ^h-1 e un ^h.

Giustificare rigorosamente questo ultimo passo può essere piuttosto noioso, ma basti dire che l'affermazione precedente sta essenzialmente dicendo che n = Θ (a ^h), che equivale a dire che h = Θ (log _a n).

Naturalmente, ciò vale per alberi perfettamente bilanciati. Se l'albero non è affatto bilanciato, il caso peggiore è h = O (n).