Compréhension du calcul de complexité

Bonjour,

pendant un entretien on m'a demandé de coder un algorithme qui calculerait l'intersection d'une liste de tableaux (notons-les L₁ à L_n). J'ai donné un algo relativement naïf qui calcule l'intersection de 2 tableaux puis ensuite l'intersection du résultat avec le tableau d'après dans la liste. Il m'a ensuite demandé d'en définir l'ordre de complexité, ce dont je suis pas très capable, donc j'ai répondu "N², peut-être N³".

Reprenons du début, pour la première intersection, on parcours le 2nd tableau L₁ fois, donc ça donne du N² ? Donc si on continue comme ça, on fera N-1 calcul d'intersection, donc N-1 fois N² ? donc une complexité N³ ?

Ensuite il m'a demandé comment il pouvait être améliorer, j'ai dit « si on ne repasse pas par les anciennes valeurs ». Et aujourd'hui j'ai implémenté cet algo:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

<?php
function getIntersectionOfArrays($arrays)
{
    $return = [];

    $indexes = [];
    //!1
    foreach($arrays as &$array)
    {
        if(count($array) == 0) // if an array is empty, intersection is empty
            return [];

        sort($array);
        $indexes[] = 0;
    }

    $currentTesting = 1;
    $numberOfArray = count($arrays);
    //!2
    while($indexes[0] < count($arrays[0]))
    {
        if($arrays[0][ $indexes[0] ] < $arrays[$currentTesting][ $indexes[ $currentTesting ] ])
        {
            $indexes[0]++;
            $currentTesting = 1;
        }
        else if($arrays[0][ $indexes[0] ] > $arrays[$currentTesting][ $indexes[ $currentTesting ] ])
        {
            $indexes[ $currentTesting ]++;
            if($indexes[ $currentTesting ] == count($array[ $currentTesting ]))
            {
                break;
            }
        }
        else
        {
            $currentTesting++;
            if($currentTesting == count($arrays))
            {
                $return[] = $arrays[0][ $indexes[0] ];
                $currentTesting = 1;
                //!3
                foreach($indexes as &$index)
                {
                    $index++;
                }
            }
        }
    }

    return $return;
}

Cet algo tient un pointeur sur chaque tableau et avance la valeur la plus faible entre celle du premier tableau et celle du tableau en cours (au début, le deuxième). Tant que les deux valeurs ne sont pas identiques, on avance la plus faible. Si elles le sont, on incrémente le tableau en cours (on compare donc le premier avec le troisième). Si elles sont toutes égales, on ajoute la valeur au tableau de retour et on avance tous les indexes. Si un des indexes dépasse de son tableau, on a fini.

Pour celui-là (ne prenons pas en compte que c'est en PHP et que array() est un faux tableau, où que j'appelle count() à chaque tour de boucle), j'imagine qu'en !1 ça donne du N×NlogN (si on considère sort comme un quicksort), donc ça donne N²logN donc N² ? Ensuite pour !2, on va parcourir chaque tableau linéairement, donc encore une fois, celà est-il bien N² ? Pour !3, étant fait seulement quand une certaine condition est respectée (toutes les valeurs identiques), c'est juste du N ? Dois-je en conclure que mon algo est en N² ? ou je me suis trompé quelque part ?

Merci.

Bonjour,

Quand on parle de complexité il faut bien identifié à quoi correspond les notations utilisées pour ta complexité ? C'est quoi ton $N$ ? Le nombre total d'élément ?

Dans bien des cas c'est assez trivial puisqu'il ne peut y avoir qu'un paramètre, mais ce n'est pas ton cas. Je considérerais bien $N$ la longueur de la liste et $M$ la plus grande longueur parmi celles de tout les tableaux de la liste.

Dans le cas de ton algorithme naïf on obtient dans le pire cas $\mathcal{O}\left(M^2N^2\right)$ si je me trompe pas ($\sum_{i=2}^NM^2(i-1)$ opérations), et on retrouve la complexité que tu donnais (puisque le nombre total d'élément pire cas est $NM$).

Je ne suis pas certain d'avoir compris le second algorithme que tu proposes. Cependant on doit pouvoir avoir une amélioration en insérant dans une structure ou la recherche est logarithmique (en temps moyen, restant linéaire en pire cas) et l'insertion au plus logarithmique.

On peut réaliser un algorithme d'union avec cette structure, dans ce cas seul le nombre total d'éléments d'éléments compte, notons le $P$, et dans ce cas une majoration de la complexité est $\mathcal{O}\left(\log^2P\right)$ (il faut calculer $\sum_{i=2}^P\log\left(i-1\right)$ opérations).

On peut aussi réaliser un algorithme d’intersection, dans ce cas avec les notations précédentes on trouve une complexité en $\mathcal{O}\left(MN\log\left(M\right)\right)$.

Pour l'union, on prends les éléments un par un, on le recherche dans la structure (dont la taille est donc au maximum de $i-1$ lorsque l'on traite le $i^{ième}$ élément), si on ne le trouve pas on l'insère.

Pour l'intersection, on joue avec deux structures, initialement on transfère le premier tableau la première structure, ensuite on prend successivement chaque éléments du deuxième tableau que l'on cherche dans la première structure, si on le trouve on l'insère dans la seconde structure. Ensuite on vide la première structure, et on fait de même avec le tableau suivant en inversant les rôles des deux structures (une où chercher et une où insérer).

Edit suite au message de QuentinC: J'ai considéré l'intersection pour calculer la complexité du premier algorithme, et celui que je propose en deuxième est pour l'union.

Bonsoir,

J'ai peut-être mal compris le problème, mais quelque chose me fait tilt :

if an array is empty, union is empty

C'est l'intersection d'un ensemble d'ensembles qui est vide si un des ensembles de départ est vide. Et dans les faits, c'est effectivement l'intersection que tu calcules dans ton code et pas l'union.

Calculer l'union de plusieurs tableaux, ça doit pouvoir se faire de manière assez triviale, en $O(n)$ avec une structure type HashSet, ou au pire en $O(n*log(n))$ avec une structure de sortie triée; où n=la taille totale de tous les tableaux de départ réunis.

Si c'est vraiment l'intersection que tu cherches, alors c'est un peu plus complexe. Ca doit pouvoir se faire en $O(n*log(n))$ en parcourant tous les tableaux (triés au préalable) en même temps. Tu n'est pas mal parti dans ce cas, c'est juste que tu devrais prendre directement tous les tableaux en même temps au lieu de deux par deux.

Freedom, j'étais parti du principe, ayant un tableau de tableau, qu'on aurait donc X tableaux de longueur L_n, et qu'en moyenne on pouvait prendre L = N (donc N² données) donc assomption fausse et donc faut prendre N comme X*max(L) ?

QuentinC, ha oui, mince, c'est bien l'intersection (pas l'union). Et je compare bien tous les tableaux en même temps: - je compare array1[x1] avec array2[x2], et seulement si c'est égal, je compare avec array3[x3]. Et tu parles de $O(n)$, mais c'est comment tu trouves cette valeur qui m'intéresse

L'algo fait ceci (crochets = cases testées, point = curseur du tableau):

1
2
3

[.1], 2, 3, 4, 5
[.1], 2, 3, 5, 7, 8
.1, 4, 5, 7, 9

1 == 1 donc on passe au tableau suivant

1
2
3

[.1], 2, 3, 4, 5
.1, 2, 3, 5, 7, 8
[.1], 4, 5, 7, 9

1 == 1 et on est au dernier tableau, on ajoute 1 à l'intersection et on avance tous les curseurs (et on recommence avec les tableaux 1 et 2)

1
2
3

1, [.2], 3, 4, 5
1, [.2], 3, 5, 7, 8
1, .4, 5, 7, 9

2 == 2, on passe au suivant, 2 < 4, donc on avance le tableau 1 et on test de nouveau avec le deuxième tableau. 3 > 2, donc on avance le 2è tableau et rebelotte, 3 < 4.

1
2
3

1, 2, 3, [.4], 5
1, 2, 3, [.5], 7, 8
1, .4, 5, 7, 9

comme 4 < 5, on avance le premier, puis ensuite 5 == 5 donc on passe au 3è, comme 4 < 5 on avance le 3è et donc on a 5 partout ce qui fait que 5 est ajouté à l'intersection. Comme le tableau 1 est arrivé à la fin. fin de l'algo.

J'ai peut-être pas compris le problème mais pourquoi ne pas utiliser une structure de multi-ensemble ?

Tu prends un dictionnaire qui associe à une lettre son nombre d'occurences.

Donc tu obtiens deux multi-ensembles pour les deux mots. Ensuite, tu as juste à prendre le min à chaque fois.

Ca donne pas un algorithme en $O(N+M)$ ? Si les multi-ensembles sont codés avec des tables de hachage.

Je ne vois pas pourquoi on a besoin de trier, ce qui me laisse supposer que j'ai pas compris…

Ok, merci à vous, le brouillard commence à se dissiper dans ma tête.

Le plus simple me semble quand même être le dictionnaire