Je teste mes connaissances :
Complexité Algorithmique

Exercice 1

Écrivez un algorithme permettant de trouver le plus grand entier présent dans un tableau. Vous ferez "tourner à la main" votre algorithme en utilisant le tableau t = [3,5,1,8,4,2]. Vous déterminerez ensuite la complexité de votre algorithme.

Réponse

Voici un algorithme possible (on supposera que la tableau comporte au moins 1 élément):

fonction plus_grand(tab : tableau)
Début
  max <-- tab[0]
  Pour ind = 1 à nbélément(tab) Faire
     Si ( tab[ind] > max ) max <-- tab[ind]
  FinPour
  Retourner max
Fin

La complexité de cet algorithme est de O(n), car l'algorithme parcourt l'ensemble des données du tableau.

Exercice 2

Écrivez un algorithme permettant de calculer la moyenne de tous les entiers présents dans un tableau. Vous ferez "tourner à la main" votre algorithme en utilisant le tableau t = [3,5,1,8,4,2]. Vous déterminerez ensuite la complexité de votre algorithme.

Réponse

Voici un algorithme possible (on supposera que la tableau comporte au moins 1 élément):

fonction moyenne(tab : tableau)
Début
  somme <-- tab[0]
  Pour ind = 1 à nbélément(tab) Faire
     somme <-- somme+tab[ind]
  FinPour
  Retourner somme/nbélément(tab)
Fin

La complexité de cet algorithme est de O(n), car l'algorithme parcourt l'ensemble des données du tableau.

Ne pas hésiter à proposer des énoncés d'exercices ... Avec corrections ;)