Compréhension du calcul de complexité

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour,

correction: intersection, pas union

pendant un entretien on m'a demandé de coder un algorithme qui calculerait l'intersection d'une liste de tableaux (notons-les L1 à Ln). 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 L1 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.

Édité par firm1

+0 -0

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.

Édité par Freedom

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.

Édité par QuentinC

Ma plateforme avec 23 jeux de société classiques en 6 langues et 13000 joueurs: http://qcsalon.net/ | Apprenez à faire des sites web accessibles http://www.openweb.eu.org/

+0 -0
Auteur du sujet

Freedom, j'étais parti du principe, ayant un tableau de tableau, qu'on aurait donc X tableaux de longueur Ln, 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.

+0 -0

Cette réponse a aidé l'auteur du sujet

J'ai édité mon précédent message suite à la remarque de QuentinC.

Je comprends mieux ton algorithmes en voyant tes schémas la complexité, de ce que tu montres, est $\mathcal{O}\left(P\right)$ (notation de mon message précédent). On considère donc que tes tableaux sont toujours triés ou pas ? Pour la démonstration, elle est direct, le pire cas est celui où tout tes tableaux sont identiques, dans ce cas tu parcours une fois l'ensemble des tableaux : $P$ opérations.

Si ils ne sont pas triés, il faut le faire en amont, soit $\mathcal{O}\left(NM\log M\right)$ (on trie $N$ tableaux de taille $M$ avec un algorithme quasi-linéaire). Ce qui est la même complexité que l'algo que je propose.

Édité par Freedom

Staff

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…

+0 -0

Cette réponse a aidé l'auteur du sujet

Et tu parles de $O(n)$, mais c'est comment tu trouves cette valeur qui m'intéresse

Le truc c'est que ça dépend aussi de ce qu'est n, et de ce que tu considères comme étant une opération significative.

Dans le cas ici, j'ai considéré le simple parcours, l'accès à la donnée si tu préfères. On parcours une seule fois tous les tableaux et leur taille cumulée est n, donc c'est un algo en $O(n)$.

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

C'est vrai que ça peut aussi marcher avec une HashMap qui associe à chaque élément son nombre d'occurence. Ce n'est toutefois pas meilleure que l'approche merge-like, ça fait aussi du $O(n)$. Par contre en ce qui concerne la mémoire je pense qu'on y perd, vu qu'il faut remplr la map, et ensuite la reparcourir entièrement pour construire la liste résultat. Peut-être qu'une technique est plus pratique que l'autre selon le langage utilisé.

Ma plateforme avec 23 jeux de société classiques en 6 langues et 13000 joueurs: http://qcsalon.net/ | Apprenez à faire des sites web accessibles http://www.openweb.eu.org/

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte