La complessità dello spazio sulla creazione di un oggetto su ricorsione il metodo

Question

checkIfBalanced() nel seguente codice restituisce true se l'albero è bilanciato e falso altrimenti. Tuttavia in ogni ricorsione crea un oggetto TreeData. A mio parere, la complessità dello spazio è O (1), poiché dopo che ogni frame dello stack è stato scoppiato, il riferimento dell'oggetto creato su quel frame dello stack è stato perso e la garbage collection. Ho ragione?

Si prega di notare:

1. io non sono alla ricerca di suggerimenti per migliorare/cambiare il mio codice. Il seguente esempio di codice è fatto su misura per porre la mia domanda.

2. Inoltre, please ignore space-complexity adding stack frames. Sto cercando la complessità spaziale degli oggetti numero 'TreeData' creati. Mi sembra che in qualsiasi punto ci sarebbero solo 3 oggetti TreeData. Questo è quello che voglio verificare. Grazie.

private static class TreeData { 
     private int height; 
     private boolean isBalanced; 

     TreeData(int height, boolean isBalanced) { 
      this.height = height; 
      this.isBalanced = isBalanced; 
     } 
    } 

    public boolean checkIfBalanced() { 
     if (root == null) { 
      throw new IllegalStateException(); 
     } 
     return checkBalanced(root).isBalanced; 
    } 

    public TreeData checkBalanced(TreeNode node) { 
     if (node == null) return new TreeData(-1, true); 

     TreeData tdLeft = checkBalanced(node.left); 
     TreeData tdRight = checkBalanced(node.right); 

     if (tdLeft.isBalanced && tdRight.isBalanced && Math.abs(tdLeft.height - tdRight.height) <= 1) { 
      return new TreeData(Math.max(tdLeft.height, tdRight.height) + 1, true); 
     } 

     return new TreeData(Math.max(tdLeft.height, tdRight.height) + 1, false); 
    } 

Answer 1

A mio spazio parere complessità è O (1) come dopo ogni frame stack è spuntato, il riferimento dell'oggetto realizzato su tale telaio stack è perso e garbage collection. Ho ragione ?

No, hai sbagliato nel presupporlo. Ray Toal ha spiegato molto bene questo. In qualsiasi punto della ricorsione, è necessario contare tutti i fotogrammi di stack interni che vengono salvati in memoria, poiché la complessità dello spazio considera in considerazione tutto lo spazio ausiliario (spazio extra) insieme all'input (non sottolineato qui).

Avanti,

Cerco complessità spaziale del numero oggetti 'TreeData' creati.

Lo spazio massimo consumata da un programma ricorsivo è proporzionale alla profondità massima di ricorsione incorniciata. La profondità massima dell'albero di ricorsione è definita come la lunghezza del percorso più lungo nell'albero.

Per il programma specificato, il programma parte dalla radice dell'albero e inizia a creare il sottoalbero sinistro e quindi controlla la sottostruttura di destra. Infine, restituirà la lunghezza del percorso più lungo e se l'albero è bilanciato o meno.

Sembra a me che in qualsiasi momento ci sarebbero solo 3 TreeData oggetti. Questo è quello che voglio verificare.

n, in qualsiasi particolare momento di esecuzione, in primo luogo tutte le sottostrutture sinistra sono verificati e quindi il giusto-sottoalberi vengono verificati, quindi il numero di oggetti di TreeData nella memoria sarebbero solo 1. Sarà ogni controllo orario perché è figlio sinistro o destro. E, quindi, tutti quelli (log n --- in caso di albero bilanciato, OR n --- in caso di albero degenerato) i nodi tranne uno continueranno ad essere impilati nella memoria. In un determinato momento, solo 1 oggetto TreeData si troverebbe nello stato attivo, altri sarebbero messi in pausa e impilati nella memoria e in attesa che il loro turno venisse visualizzato.

Answer 2

Tuttavia in ogni ricorsione si crea oggetto TreeData.

Non vero. Crei solo il nuovo oggetto TreeData nel caso base della tua ricorsione. Se sei preoccupato di questo, perché non hai solo un'istanza finale statica TreeData dichiarata una volta nella classe che puoi usare. Dopotutto, l'unica cosa che stai propagando da questo Nodo è il valore booleano isBalanced.

È anche possibile propagare direttamente il valore booleano se si modifica la firma del metodo per restituire un valore booleano.

Answer 3

Non si sta utilizzando la ricorsione della coda qui e si stanno costruendo riquadri di impilamento mentre si recita l'albero. Per essere onesti, conta quei telai dello stack. Se il tuo albero è bilanciato, creerai i fotogrammi dello stack n di registro mentre ricorri. Nel peggiore dei casi, con un albero completamente degenerato, potresti avere fino a n frame di stack.