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 c : Sélectionner tout - Visualiser dans une fenêtre à part
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