Inscription / Connexion Nouveau Sujet
Tableau inclus dans un autre
Bonjour.
Pour un exercice, il faut écrire un algorithme ayant en entrée deux tableaux A et B qui décide si tout
élement de A est élement de B de complexité en temps dans le pire des cas minimale. J'ai pensé à deux méthodes pour cela, qu'en pensez vous?
1. Par un algorithme dynamique : on crée un tableau vide T. On parcourt le tableau A, et pour chaque élément, s'il appartient à T, on ne fait rien, s'il n'appartient pas à T, on regarde s'il appartient à B. Le problème c'est que je ne suis pas sûr que cela améliore la complexité en temps DANS LE PIRE DES CAS.
2. On trie A et B. Ensuite on peut les parcourir parallèlement et de façon ordonnée. Je n'ai pas écrit l'algorithme mais il me semble que la complexité en temps serait de |B|. Pour un tri optimal, la complexité en temps est |B|.log(|B|). Du coup on se retrouve avec un algorithme en |B|.log(|B|).
Merci.
Bonjour,
Je serais également en faveur de la seconde solution. Le premier algorithme, si j'ai bien compris, consiste à considérer chaque élément de A puis à parcourir B pour vérifier s'il y est présent (mais je ne vois pas l'intérêt du tableau T dans ce cas).
Le second algorithme présente l'avantage de pouvoir être optimisé par le bon choix de la méthode de tri. Une question: j'imagine que la taille de B est éventuellement supérieure à celle de A ?
Cordialement.
Merci de ta réponse.
En fait, le tableau T dans le premier algorithme permet de ne pas tester deux fois la présence d'un même élément dans le tableau B. Cela permet d'éviter des grandes complexités dans les cas où par exemple le tableau B est de taille très grande, ou si le tableau A ne contient qu'un élément se répétant de nombreuses fois. Mais comme je l'ai dit, il s'agit ici d'améliorer la complexité dans le pire des cas, donc ça ne semble pas utile ici.
Il n'y a pas de précision sur les tailles de A et B(donc tous les cas sont possibles j'imagine).
Bonne journée.
Annuler
connectez vous