[Algo] Recherche maximum dans matrice 2D
Bonsoir,
Je suis entrain de réfléchir à la création d'un algorithme performant permettant de trouver dans une matrice N*M de nombres entiers le maximum, le plus rapidement possible c'est à dire en faisant le moins d'opérations possibles (complexité faible).
Bien sur, on connait tous l'algo le moins performant en O(n^2) :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
int max(int** a)
{
int i,j;
int mymax = a[0][0];
for (i = 0; i < LIG; i++)
{
for (j = 0; j < COL; j++)
{
if (a[i][j] > mymax)
{
mymax = a[i][j];
}
}
}
return mymax;
} |
La matrice pouvant être très grande, cet algo n'est pas envisageable !
Voilà, je pense que ca doit demander un bon niveau en maths mais si vous avez des pistes, je suis preneur.
J'ai pensé à l'utilisation d'un arbre binaire (équilibré), ou alors à utiliser un algo de tri performant (quicksort), voire une pile/file, un tas binaire...
Merci à vous, et bonne soirée :)
