Bonjour,
J'ai une fonction, je peux l'écrire de deux façons différentes, et je cherche la meilleur en complexité.
Note : c'est de la prog fonc, donc sans affectation.
Le contexte :
Les arbres lexicographiques i.e. des arbres n-aires où chaque noeud est étiqueté par un booléen indiquant si le sous-arbre qui commence à ce noeud contient le mot vide, et chaque branche est étiqueté par des lettres.
Grosso-modo, mon type est défini comme ceci :Globalement ça dit que lextree est une structure avec un booléen et une table, et que la table contient une liste de couple (lettre, arbre).
Code ocaml : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5 type 'a lextree = { has_epsilon : bool ; table : 'a table } and 'a table = ('a * 'a lextree) list ;;
J'ai écrit une fonction qui prend un arbre t et un début de mot w et qui doit retourner la liste des mots (sous forme de liste de liste de lettres) contenu dans t en les préfixant par w.
Elle est actuellement écrite comme ceci (à peu de choses près) :
Le @ représente l'opération de concaténation. C'est à dire qu'il parcours la liste w pour y ajouter la liste contenant uniquement l'élément x. Et bien sûr, comme on est dans un langage fonctionnel, il va y avoir autant de création de cellules de liste qu'il y avait de lettres dans w.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9 iterate t w: Si t.epsilon alors ajouter le mot w à la liste résultat fsi pour chaque couple (x, lex) de t.table iterate lex w@[x] fpour
Elle n'apparaît pas ici, mais en fait il y a une liste résultat en paramètre supplémentaire à la fonction pour ajouter les mots sans faire de concaténation.
J'ai essayé de déterminer la complexité de cette fonction en nombre de création de cellules de liste.
Si on appel n le nombre de mots dans le lextree, et m la taille moyenne d'un mot. (as-t-on m ~= log n ?)
On a au minimum n créations de cellules pour ajouter les mots dans la liste résultat.
Ce à quoi il faut rajouter le nombre de création de cellules dûes aux concaténations de w et [x].
Pour rappel l1@l2 crée autant de cellules qu'il y en avait dans l1.
J'ai envie de dire n*m^2, mais je suis pas sûr.
La deuxième version consiste à stocker w à l'envers pour avoir juste une création de cellule à la place de la concaténation quand on rajoute une lettre dans w.
Par contre, il faudra remettre la liste à l'endroit avant de l'ajouter dans la list, et ça c'est en O(m). Donc rien que remettre les listes à l'endroit avant concaténation dans la liste résultat donne un algo en O(n*m). Ce à quoi il faut rajouter la construction de cellules pour rajouter les lettres au début de w quand on descend les appels récursifs.
Mais là, pour ça je bug un peu.
Comme c'est un arbre, on réutilise le w en paramètre, donc y'a beaucoup moins que n*m opérateur cons (ou ::, construction de cellule) pour construire le mot...
Je pense qu'au final les deux algos ont des complexité équivalentes, mais juste pour le fun, j'aimerai savoir ce que c'est.
Merci d'avance.
Partager