Come calcolare la complessità dello spazio per SubTree binario Ricerca

Question

Questo problema viene dal libro Cracking the Coding Interview. Ho difficoltà a capire la complessità dello spazio della soluzione.

Problema:
Ci sono due grandi alberi binari: T1, con milioni di nodi, e T2, con centinaia di nodi. Crea un algoritmo per decidere se T2 è un sottoalbero di T1.

Solution (in Java):

public static boolean containsTree(TreeNode t1, TreeNode t2) { 
    if (t2 == null) 
     return true; // The empty tree is a subtree of every tree. 
    else 
     return subTree(t1, t2); 
} 

/* Checks if the binary tree rooted at r1 contains the binary tree 
* rooted at r2 as a subtree somewhere within it. 
*/ 
public static boolean subTree(TreeNode r1, TreeNode r2) { 
    if (r1 == null) 
     return false; // big tree empty & subtree still not found. 
    if (r1.data == r2.data) { 
     if (matchTree(r1,r2)) return true; 
    } 
    return (subTree(r1.left, r2) || subTree(r1.right, r2)); 
} 

/* Checks if the binary tree rooted at r1 contains the 
* binary tree rooted at r2 as a subtree starting at r1. 
*/ 
public static boolean matchTree(TreeNode r1, TreeNode r2) { 
    if (r2 == null && r1 == null) 
     return true; // nothing left in the subtree 
    if (r1 == null || r2 == null) 
     return false; // big tree empty & subtree still not found 
    if (r1.data != r2.data) 
     return false; // data doesn’t match 
    return (matchTree(r1.left, r2.left) && 
      matchTree(r1.right, r2.right)); 
} 

Il libro dice la complessità spazio di questa soluzione è O (log (n) + log (m)) dove m è la numero di nodi in T1 (albero più grande) e n numero di nodi in T2.

Per me, è sembra che la soluzione ha O (log (m) * log (n)) complessità spaziale poiché la funzione "sotto-albero" ha log (n) chiamate ricorsive e ogni chiamata ricorsiva esegue "matchTree "funzione che attiva log (m) chiamate ricorsive.

Perché la soluzione O (log (n) + log (m)) è complessa?

Answer 1

Poiché non stiamo creando alcun oggetto sull'heap, la complessità dello spazio è la dimensione della pila. Quindi la domanda non è quante chiamate totali si verificano, ma quanto grande può crescere lo stack.

containsTree() può chiamare solo subTree(), subTree() può chiamare se stesso o matchTree() e matchTree() può solo chiamare se stesso. Quindi, in qualsiasi punto in cui matchTree() è stato chiamato, lo stack è simile al seguente:

[containsTree] [subTree] ... [subTree] [matchTree] ... [matchTree] 

Questo è il motivo per cui non si moltiplicano le complessità dello spazio qui: mentre ogni chiamata a subTree() può chiamare matchTree(), quelle chiamate a matchTree() congedo la pila prima di subTree() continua a ricorrere.

Analisi lungo le linee della "risposta corretta"

Se la domanda non specifica se gli alberi sono in equilibrio, poi una vera e propria analisi del caso peggiore sarebbe assumere essi potrebbero non essere. Tuttavia, tu e il libro state supponendo che lo siano. Siamo in grado di mettere da parte questa domanda per poi dicendo che la profondità di T1 è c, e la profondità di T2 è d. c è O (log (m)) se T1 è equilibrata, e O (m) altrimenti. Stessa cosa per T2's d.

caso peggiore per matchTree() è O (d), perché la più lontana potrebbe ricorsione sarebbe il colmo di T2.

caso peggiore per subTree() è O (c) per la sua ricorsione, perché la più lontana potrebbe ricorsione sarebbe il colmo di T1, più il costo della chiamata matchTree(), per un totale di O (c + d).

E containsTree() aggiunge solo una costante in cima alla chiamata subTree(), in modo da non modificare la complessità dello spazio.

Quindi, se entrambi T1 e T2 sono equilibrati, sostituendo c e d si può vedere che O (log (m) + log (n)) sembra ragionevole.

Problemi con la "risposta corretta"

come ho detto prima, non è giusto supporre alberi binari sono in equilibrio finché non si sa per certo che essi sono. Quindi una risposta migliore potrebbe essere O (m + n).

Ma aspetta! La domanda indica che la dimensione di T2 è inferiore alla dimensione di T1. Ciò significa che n è O (m), e log (n) è O (log (m)). Allora, perché abbiamo perso tempo a preoccuparci di n?

Se gli alberi sono bilanciati, la complessità dello spazio è semplicemente O (log (m)). Nel caso generale in cui non si sa cosa sia bilanciato o meno, la vera risposta dovrebbe essere O (m), la dimensione dell'albero più grande.