La complessità temporale della costruzione di un albero binario dagli attraversamenti inorder e preorder - c ++, c, algoritmo

Dato Qui è il codice per costruire un albero dalattraversamenti inorder e preorder. Non riesco a capire come siano arrivati ​​a una complessità temporale O (n ^ 2). Qualche idea? Vedo che la ricerca di un indice nella sequenza inorder sarebbe O (n), come viene calcolato il resto?

risposte:

Il O(N^2) la complessità deriva dal fatto che per ogni elemento nell'attraversamento del preordine (di cui esistono N), devi cercare la sua partizione nel traverso Inorder, (di nuovo ci sono N di questi).

In parole povere, puoi considerare questo algoritmo come posizionare i nodi su una griglia, dove l'attraversamento Inorder fornisce le coordinate x e l'attraversamento Preorder fornisce le coordinate y:

Prendi l'esempio che hanno fornito, con i seguenti attraversamenti (Inordine, quindi Preordine):

Inorder: DBEAFC
Preorder: ABDECF

Ora questa è la griglia su cui vengono posizionati:

     D    B    E    A    F    C
A    +    +    +    A    |    |
|    +--------------+    |
B|F  +    B    |         F    |
+---------+         -----+
DE|C D         E              C

Ora, l'algoritmo deve sapere dove posizionare nella griglia ciascun nodo, cosa che fa semplicemente posizionando il nodo nella posizione nella griglia in cui le coordinate xey sono le stesse.

Sembra che la dimensione della griglia sia effettivamente NlogN in questo caso, che si tradurrebbe in un NlogN complessità per attraversare la griglia (e così un NlogN complessità temporale per l'algoritmo) ma questo albero è equilibrato. Nel peggiore dei casi, l'albero potrebbe in effetti essere un elenco collegato.

Per esempio. considera questo albero, dove gli attraversamenti preordine e inorder sono gli stessi:

Inorder: DBEAFC
Preorder: DBEAFC

D    B    E    A    F    C
D    D    |    |    |    |    |
-----+    |    |    |    |
B         B    |    |    |    |
-----+    |    |    |
E              E    |    |    |
-----+    |    |
A                   A    |    |
-----+    |
F                        F    |
-----+
C                             C

Questo è il caso peggiore, e vedete, la griglia ha N*N posizioni in esso per verificare. Quindi, nel peggiore dei casi, c'è un N*N complessità temporale.

stai attraversando il tutto preorder array all'interno della ricorsione e in ogni frame dello stack in cui stai cercando un numero inorder matrice trasversale. Così O(N*N) = o(N^2).