Quel est le temps d'exécution de mon algorithme?

Question

J'écris un algorithme qui va d'abord prendre un fichier de configuration de divers paramètres et leur méthode associée comme suit:

/guest guestEndpoint 
/guest/lists listEndpoint 
/guest/friends guestFriendsEndpoint 
/guest/X/friends guetFriendsEndpoint 
/guest/X/friends/X guestFriendsEndpoint 
/X/guest guestEndpoint 
/X/lists listEndpoint 
/options optionsEndpoint 

X représente ici un caractère générique, de sorte que toute chaîne correspondrait à cela. L'algorithme prend cela comme entrée et construit un arbre avec chaque noeud représentant un jeton entre les /. Chaque feuille serait un point de terminaison valide.

Ensuite, lorsque l'utilisateur passe quelque chose comme guest/abc/friends il traverserait l'arbre à partir de la racine, puis chercher un nœud guest attaché à la racine, si elle existe aller au noeud guest, si guest ici invité aurait un wildcard nœud, donc si abc ne correspond pas avec l'un des nœuds de guest, mais il y avait un nœud wildcard présent, il irait à la wildcard. Ensuite, il regarderait de wildcard pour voir s'il avait un nœud friends, si c'est le cas, allez-y. Ensuite, si friends est un nœud feuille, il renvoie la méthode correspondante.

Cet algorithme a-t-il un sens? Je me demande quelle serait la durée de la recherche. Je pense que ce serait O (n) où n est le nombre de jetons dans le param qui a été passé.

Voici une image du graphique que je construirais en fonction de l'entrée ci-dessus. Chaque diamant représente une méthode de point final.

Merci pour toute aide!

Answer 1

Le plus mauvais temps de recherche sera O (E + N) où E est un nombre si les arêtes et N est le nombre de noeuds. Becuase Nous ne savons pas combien de nœuds sont présents à chaque niveau. Donc, par votre algorithme, vous trouvez le premier nœud dans la séquence désirée en effectuant une recherche de niveau car vous n'avez aucun paramètre à vérifier pour passer par le chemin désiré. (Je sais que le nombre de nœuds va diminuer à chaque fois que je descends d'un niveau mais de combien est incertain dans ce cas) Ce n'est même pas n-array.

La carte générique n'aidera pas à réduire la complexité temporelle du pire des cas et sera incertaine de connaître le meilleur cas d'un arbre. La vérification des caractères génériques prend un temps constant et ne comptera pas dans le temps d'exécution.

maintenant algorithme semble peu confus que ferez-vous lorsque vous avez deux options

1) vous avez nœud naturel associé 2) vous avez noeud de wild card.

Sur le même niveau, où allez-vous? Supposons que vous alliez dans la direction que vous avez d'abord rencontrée. Mais que se passe-t-il si ce n'est pas le chemin réel que vous arrivez à connaître au dernier nœud, donc vous le retournez en arrière. Pour éviter cela, vous garderez la marque du nombre de chemins disponibles à chaque niveau par BFS et ferez la recherche. La complexité du temps de cas le plus défavorable serait donc O (E + N) à condition que vous ayez traité tous les cas.