On appelle MINIMAX d'une matrice d'entiers la valeur
minimale des maxima de chaque ligne.
- Ecrire un algorithme qui donne la valeur MINIMAX
d'une matrice d'entiers nXm ainsi que l'emplacement du
MINIMAX dans cette
matrice. On précisera la nature de l'algorithme (fonction ou
procédure) ainsi que le type et les modes de passages des paramètres.
L'algorithme est une procédure. Les paramètres sont :
- la matrice M passée par référence pour ne pas provoquer de copie en mémoire
- les dimensions n et m de la matrice passées par valeur,
- les résultats sont passés par référence MM la valeur recherchée,
L et C la position ligne colonne de MM.
procédure MinMax(ref M:tableau[1..n,1..m] d'entiers;
val n,m:entiers;
ref MM,L,C: entiers);
var iL,iC,CMax:entiers;
début
L:=1;C:=1;
pour iL allant de 1 à n faire
CMax:=1;
pour iC allant de 1 à m faire
si M[iL,iC]>M[iL,CMax] alors
CMax:=iC
finsi
finpour;
si M[L,C]>M[iL,CMax] alors
L:=iL;C:=CMax;
finsi
finpour;
MM:=M[L,C];
finprocedure
- Evaluer la complexité de votre l'algorithme (on précisera
l'opération pertinente servant à évaluer cette complexité qui pourra
être, ici, la comparaison de deux éléments de la matrice).
Il y a deux boucles pour imbriquées et chacune comporte un test donc la complexité est nm.
- Peut-on améliorer la complexité de cet algorithme en
triant chaque ligne de la matrice ?
Si la matrice n'est pas triée, cela veut dire que l'on trierait chaque ligne.
la complexité du tri (puisqu'on ne connait pas des bornes a priori des entiers) est mlog(m).
Par suite la complexité de la procédure deviendrait nmlog(m) ce qui est moins bon en complexité.