Discussion :

[Amy234]

Bonjour,

J'ai besoin de votre aide pour un exercice sur les complexités, je suis bloqué dès la première partie!

Voici le début mon travail, je ne sais pas si mes réponses sont correctes.

1) somme de i pour i allant de 0 à (n-1) = ((n-1)n) / 2.

2) dans le pire le tableau est trié donc A[i]>key n'est jamais valide donc le nombre minimal de comparaison est n.

3) la ligne 2, 3 et 7 seront exécuté n fois
la boucle est exécuté, dans le pire cas, ((n-1)n) / 2 fois
donc en somme 3n + ((n-1)n) / 2 fois
j'en déduit que la complexité est de Θ(n^2)

4) aucune idée

5) aucune idée


Si certains auraient des pistes pour moi... Merci bien de votre aide!

[CodeurPlusPlus]

Un petit indice pour les questions 4 et 5 : la fonction strcmp compare les chaînes par ordre lexicographique.