Discussion :

[Aspic]

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

[FR119492]

Salut!

Tout d'abord, ça n'est pas une matrice, mais un tableau.

Ensuite, où se trouve ce tableau: déjà dans ton programme ou sur un fichier que tu dois lire?

Jean-Marc Blanc

[PRomu@ld]

En fait, ton algo est optimal (il est d'ailleurs en O(N*M) et pas N^2)) si tu n'as aucun a priori sur la matrice tu es obligé de tester tous les éléments donc tu ne peux pas faire mieux.

Utiliser un algorithme de tri va transformer ton algo en un algo en O( (N*M) log( N*M) ) donc pire. Je le répète : si tu n'as aucun a priori sur ta matrice, tu dois tester tous les éléments donc il n'y a pas mieux que ce que tu as présenté.

[prgasp77]

Pour appuyer l'argumentation de promuald, sache que si tu veux faire moins de n*m-1 tests, cela signifie que tu ne testera pas au moins un des entiers. Mais peut-être peux-tu faire quelques suppositions raisonnables sur ta matrice ?

[Aspic]

En fait, ton algo est optimal (il est d'ailleurs en O(N*M) et pas N^2)) si tu n'as aucun a priori sur la matrice tu es obligé de tester tous les éléments donc tu ne peux pas faire mieux.

Utiliser un algorithme de tri va transformer ton algo en un algo en O( (N*M) log( N*M) ) donc pire. Je le répète : si tu n'as aucun a priori sur ta matrice, tu dois tester tous les éléments donc il n'y a pas mieux que ce que tu as présenté.

Bonjour,

Oui tu as raison, j'ai supposé à tord que le nombre de lignes et de colonnes étaient identiques
Et je suis d'accord pour le tri, ca complexifé l'algorithme.
Je suis étonné qu'il n'y ait pas d'autres méthodes que la comparaison de chaque cellule, mais je comprends le principe si tous les chiffres sont entièrement soumis au hasard, on doit tous les tester...

Alors je n'ai pas plus d'info sur mon problème donc j'attends pour vous dire quels seraient les "a priori" sur la matrice car oui, les chiffres ne sont pas uniquement le fruit du hasard

PS : Un matrice et un tableau 2D pour moi c'est la même chose

PS2 : Peut importe la matrice pour se trouver dans un fichier ou dans le programme, ca ne change rien au problème.

Merci !

[Alikendarfen]

Est-ce que ta matrice (ou ton tableau) contient beaucoup de zéro ?

[ToTo13]

En fait, ton algo est optimal (il est d'ailleurs en O(N*M) et pas N^2)) si tu n'as aucun a priori sur la matrice tu es obligé de tester tous les éléments donc tu ne peux pas faire mieux.

Utiliser un algorithme de tri va transformer ton algo en un algo en O( (N*M) log( N*M) ) donc pire. Je le répète : si tu n'as aucun a priori sur ta matrice, tu dois tester tous les éléments donc il n'y a pas mieux que ce que tu as présenté.

+1, on ne peut faire mieux, à moins d'avoir des informations a priori sur le tableau.

[Nebulix]

La matrice pouvant être très grande, cet algo n'est pas envisageable !

Le remplissage de ta matrice est de même complexité. Si tu peux remplir ta matrice, tu peux faire les comparaisons.
si tu n'as besoin de calculer qu'un petit nombre d'éléments de ta matrice, le mieux est de calculer les extréma à la volée.

[FR119492]

Salut!

Ensuite, où se trouve ce tableau: déjà dans ton programme ou sur un fichier que tu dois lire?

Tu n'as pas répondu à cette question qui me semble essentielle.
Jean-Marc Blanc

[prgasp77]

Tu n'as pas répondu à cette question qui me semble essentielle.

PS2 : Peut importe la matrice pour se trouver dans un fichier ou dans le programme, ca ne change rien au problème.

Je pense qu'il attend une argumentation de ta part que cela influe sur la manière de résoudre le problème.

Cordialement,

[Alikendarfen]

Dans ce cas, le format du fichier lui même change l'approche du tout au tout...

[Aspic]

Bonjour à tous,

Je n'ai pas plus d'infos sur le problème, j'essaye d'en obtenir à savoir comment la matrice est remplie en amont.
Elle ne se trouve pas dans un fichier mais directement dans le programme et elle est déjà remplie par un algo complexe (une sorte de boite noire) qui retourne une matrice 2D de float.

Selon, moi une approche par dichotomie 3D pourrait être envisageable si on arrive à déterminer des postulats sur la matrice. D'après ce qu'on m'a dit le maxima à plus de chance de se trouver vers le centre que sur les bords...

J'essaye d'en apprendre plus car là, on est bloqué par manques d'infos !

Merci à tous

[FR119492]

Salut!

Je n'ai pas plus d'infos sur le problème, j'essaye d'en obtenir à savoir comment la matrice est remplie en amont.
Elle ne se trouve pas dans un fichier mais directement dans le programme et elle est déjà remplie par un algo complexe (une sorte de boite noire) qui retourne une matrice 2D de float.

C'est exactement l'information que j'attendais: si tu n'as pas accès au mécanisme de création de ton tableau, je pense que la réponse de PRomu@ld est tout à fait correcte. En revanche, si tu l'avais lu sur un fichier, il aurait été possible d'économiser un peu de temps en combinant la lecture du fichier avec la recherche de l'extrémum. En outre, il n'aurait peut-être pas été nécessaire de garder en mémoire tout le tableau.
Enfin, si tu trouves le code pour le remplissage de ton tableau, envisage de chercher le maximum pendant le remplissage et non après.
Jean-Marc Blanc