20. Exercices sur la complexité⚓︎
Question 1
Écrire un algorithme appelé distance
:
- qui renvoie -1 si deux mots ne sont pas de la même taille
- qui renvoie le nombre de lettres différentes à la même position sinon.
Exemple
mentor
et montre
ont une différence de 3.
bide
et aide
ont une différence de 1.
Quelle est la complexité de votre algorithme ?
Question 2
Quelle est la complexité du programme python ci-dessous, où dictionnaire
est un tableau contenant N mots ?
def gen_graphe(dictionnaire):
g = Graphe_dico()
for mot_1 in dictionnaire:
for mot_2 in dictionnaire:
if distance(mot_1, mot_2) == 1:
g.ajouteArc(mot1, mot2)
return g
Question 3
On donne ci-dessous l'algorithme du tri par insertion.
n ← nombre d'éléments du tableau
pour i allant de 1 à n-1 inclus:
valeur_frontiere ← tableau[i]
j ← i-1
tant que j>=0 et valeur_frontiere < tableau[j]:
tableau[j+1] ← tableau[j]
j ← j-1
tableau[j+1] ← valeur_frontiere
renvoyer tableau
- Décrire le principe de fonctionnement de cet algorithme.
- Quel serait le meilleur des cas ? et la complexité dans ce cas ?
- Quel serait le pire des cas ? et la complexité dans ce cas ?
Question 4
Soit le tableau [2, 4, 6, 8, 12, 16, 17, 22, 67, 87, 112, 141, 155, 167, 178]
.
Dessiner un arbre représentant toutes les possibilités lorsque l'on recherche un nombre.
En déduire la complexité de la recherche dichotomique.
Question 5
Quel est le principe de fonctionnement du tri par sélection ?
Donner sa complexité.
Question 6
Quelle est la complexité de la fonction suivante :
def nb_zeros(n):
resultat = 0
while n % 10 == 0:
n = n // 10
resultat += 1
return resultat
Question 7
Quelle est la complexité de la fonction suivante :
def negatif(image):
'''renvoie le négatif de l'image sous la forme d'une liste de listes'''
hauteur_img, largeur_img = hauteur(image), largeur(image)
nouvelle_image = [[0 for j in range(largeur_img)] for i in range(hauteur_img)]
for i in range(hauteur_img):
for j in range(largeur_img):
nouvelle_image[i][j] = 255 - image[i][j]
return nouvelle_image
Question 8
Quelle est la complexité de la fonction suivante :
def perm_rec(liste, pris):
if len(pris) == len(liste):
return [pris.copy()]
else:
liste_permutations = []
for element in liste:
if element not in pris:
pris.append(element)
for permut in perm_rec(liste, pris):
liste_permutations.append(permut)
pris.pop()
return liste_permutations