Exercice

Voici deux algorithmes qui cherchent l'indice du maximum d'une liste :

1
Algo IndMax1:
2
3
Entrée:
4
    l, liste d'entiers
5
6
max prend la valeur l[1]
7
ind_max prend la valeur 1
8
Pour i de 2 à longueur(l) alors:
9
    Si max < l[i] alors:
10
        max prend la valeur l[i]
11
        ind_max prend la valeur i
12
    FinSi
13
FinPour
14
15
Retourner ind_max
1
Algo IndMax2:
2
3
Entrée:
4
    l, liste d'entiers
5
6
max prend la valeur l[1]
7
Pour i de 2 à longueur(l) alors:
8
    Si max < l[i] alors:
9
        max prend la valeur l[i]
10
    FinSi
11
FinPour
12
13
Pour i de 1 à longueur(l) alors:
14
    Si l[i] == max alors:
15
        Retourner i
16
    FinSi
17
FinPour
Question
Quel algorithme a la plus petite complexité en temps ?
Solution
IndMax1 car il ne possède qu'une boucle.
Question
Quel algorithme à la plus petite complexité en espace ?
Solution
IndMax2 car il ne possède une variable de moins
Question
Combiner ces deux algorithmes pour trouver un algorithme avec une seule boucle et une seule variable.
Solution
1
Algo IndMax3:
2
3
Entrée:
4
    l, liste d'entiers
5
6
ind_max prend la valeur 1
7
Pour i de 2 à longueur(l) alors:
8
    Si l[ind_max] < l[i] alors:
9
        ind_max prend la valeur i
10
    FinSi
11
FinPour
12
13
Retourner ind_max