Complexité temporelle de la construction d’un arbre binary à partir de traversées en ordre et en pré-commande

Given Voici le code pour construire un arbre à partir des traversées en ordre et en pré-commande. Je ne peux pas comprendre comment ils sont arrivés à une complexité en temps O (n ^ 2). Des idées? Je vois que la recherche d’un index dans la séquence dans l’ordre serait O (n), comment le rest est-il calculé?

La complexité de O(N^2) résulte du fait que pour chaque élément de la traversée de pré-ordre (il y en a un), vous devez rechercher sa partition dans la traversée de l’ordre (encore une fois, il y en a N ).

En gros, vous pouvez considérer cet algorithme comme plaçant les nœuds sur une grid, où le parcours dans l’ordre fournit les coordonnées x et le parcours dans le précommande fournit les coordonnées y:

Prenons l’exemple qu’ils ont donné, avec les traversées suivantes (en ordre puis en pré-commande):

 Inorder: DBEAFC Preorder: ABDECF 

Maintenant, voici la grid sur laquelle ils sont mis:

  DBEAFC A + + + A | | | +--------------+ | B|F + B | F | +---------+ -----+ DE|CDEC 

À présent, l’algorithme doit savoir où placer chaque nœud dans la grid, ce qu’il fait simplement en le plaçant à la position dans la grid où les coordonnées x et y sont identiques.

Il semble que la taille de la grid soit en réalité NlogN dans ce cas, ce qui entraînerait une complexité NlogN pour parcourir la grid (et donc une complexité temporelle NlogN pour l’algorithme), mais cet arbre est équilibré . Dans le pire des cas, votre arbre pourrait en fait être une liste chaînée.

Par exemple, considérons cet arbre, où les traversées de précommande et d’ordre sont les mêmes:

 Inorder: DBEAFC Preorder: DBEAFC DBEAFC DD | | | | | -----+ | | | | BB | | | | -----+ | | | EE | | | -----+ | | AA | | -----+ | FF | -----+ CC 

C’est le pire des cas, et vous voyez, la grid a N*N positions à vérifier. Donc, dans le pire des cas, il existe une complexité temporelle N*N

vous parcourez tout le tableau de preorder à l’intérieur de la récursion et dans chaque cadre de stack, vous recherchez un nombre dans un tableau de passage dans l’ordre. Donc, O(N*N) = o(N^2) .

vous avez absolument raison, car la recherche dans le tableau dans l’ordre prendra O (n) fois

Dans le pire des cas, T (n) = T (n-1) + O (n)

en résolvant cela nous obtenons T (n) = O (n²)