Pourquoi le pire des cas pour cette fonction O (n ^ 2)?

J'essaie de m'apprendre à calculer la notation BigO pour une fonction arbitraire. J'ai trouvé cette fonction dans un manuel. Le livre affirme que la fonction est O (n ² ). Cela explique pourquoi, mais j'ai du mal à suivre. Je me demande si quelqu'un pourrait peut-être me montrer le calcul derrière la raison. Fondamentalement, je comprends que c'est quelque chose de moins que O (n ³ ), mais je ne pouvais pas atterrir indépendamment sur O (n ² )

Supposons qu'on nous donne trois séquences de nombres, A, B et C. Nous supposerons qu'aucune séquence individuelle ne contient de valeurs en double, mais qu'il peut y avoir des nombres dans deux ou trois séquences. Le problème de la disjonction des ensembles à trois voies est de déterminer si l'intersection des trois séquences est vide, à savoir qu'il n'y a pas d'élément x tel que x ∈ A, x B et x ∈ C.

D'ailleurs, ce n'est pas un problème de devoirs pour moi - ce navire a navigué il y a des années:), juste moi essayant d'être plus intelligent.

def disjoint(A, B, C):
        """Return True if there is no element common to all three lists."""  
        for a in A:
            for b in B:
                if a == b: # only check C if we found match from A and B
                   for c in C:
                       if a == c # (and thus a == b == c)
                           return False # we found a common value
        return True # if we reach this, sets are disjoint

[Edit] Selon le manuel:

Dans la version améliorée, nous ne gagnons pas simplement du temps si nous avons de la chance. Nous affirmons que le temps d'exécution le plus défavorable pour disjoint est O (n ² ).

L'explication du livre, que j'ai du mal à suivre, est la suivante:

Pour prendre en compte le temps d'exécution total, nous examinons le temps d'exécution de chaque ligne de code. La gestion de la boucle for sur A nécessite O (n) temps. La gestion de la boucle for sur B représente un total de O (n ² ) fois, puisque cette boucle est exécutée n fois. Le test a == b est évalué O (n ² ) fois. Le reste du temps passé dépend du nombre de paires correspondantes (a, b). Comme nous l'avons noté, il y a au plus n paires de ce type, et la gestion de la boucle sur C ainsi que les commandes contenues dans le corps de cette boucle utilisent au plus O (n ² ) fois. Le temps total passé est O (n ² ).

(Et pour donner le crédit qui convient ...) Le livre est: Structures de données et algorithmes en Python par Michael T. Goodrich et. tous, Wiley Publishing, p. 135

[Edit] Une justification; Ci-dessous le code avant optimisation:

def disjoint1(A, B, C):
    """Return True if there is no element common to all three lists."""
       for a in A:
           for b in B:
               for c in C:
                   if a == b == c:
                        return False # we found a common value
return True # if we reach this, sets are disjoint

Dans ce qui précède, vous pouvez clairement voir qu'il s'agit de O (n ³ ), car chaque boucle doit fonctionner au maximum. Le livre affirmerait que dans l'exemple simplifié (donné en premier), la troisième boucle n'est qu'une complexité de O (n ² ), de sorte que l'équation de la complexité va comme k + O (n ² ) + O (n ² ) qui donne finalement O (n ² ).

Bien que je ne puisse pas prouver que tel est le cas (d'où la question), le lecteur peut convenir que la complexité de l'algorithme simplifié est au moins inférieure à celle de l'original.

[Edit] Et pour prouver que la version simplifiée est quadratique:

if __name__ == '__main__':
    for c in [100, 200, 300, 400, 500]:
        l1, l2, l3 = get_random(c), get_random(c), get_random(c)
        start = time.time()
        disjoint1(l1, l2, l3)
        print(time.time() - start)
        start = time.time()
        disjoint2(l1, l2, l3)
        print(time.time() - start)

Rendements:

0.02684807777404785
0.00019478797912597656
0.19134306907653809
0.0007600784301757812
0.6405444145202637
0.0018095970153808594
1.4873297214508057
0.003167390823364258
2.953308343887329
0.004908084869384766

La seconde différence étant égale, la fonction simplifiée est bien quadratique:

[Edit] Et encore une preuve supplémentaire:

Si je suppose le pire des cas (A = B! = C),

if __name__ == '__main__':
    for c in [10, 20, 30, 40, 50]:
        l1, l2, l3 = range(0, c), range(0,c), range(5*c, 6*c)
        its1 = disjoint1(l1, l2, l3)
        its2 = disjoint2(l1, l2, l3)
        print(f"iterations1 = {its1}")
        print(f"iterations2 = {its2}")
        disjoint2(l1, l2, l3)

rendements:

iterations1 = 1000
iterations2 = 100
iterations1 = 8000
iterations2 = 400
iterations1 = 27000
iterations2 = 900
iterations1 = 64000
iterations2 = 1600
iterations1 = 125000
iterations2 = 2500

En utilisant le second test de différence, le résultat le plus défavorable est exactement quadratique.

Le livre est en effet correct et fournit un bon argument. Notez que les timings ne sont pas un indicateur fiable de la complexité algorithmique. Les timings peuvent ne prendre en compte qu'une distribution de données spéciale, ou les tests peuvent être trop petits: la complexité algorithmique décrit uniquement la manière dont l'utilisation des ressources ou le temps d'exécution dépasse une taille d'entrée suffisamment grande.

Le livre avance l'argument selon lequel la complexité est O (n²) car la if a == bbranche est entrée au plus n fois. Cela n’est pas évident car les boucles sont toujours écrites comme étant imbriquées. C'est plus évident si on l'extrait:

def disjoint(A, B, C):
  AB = (a
        for a in A
        for b in B
        if a == b)
  ABC = (a
         for a in AB
         for c in C
         if a == c)
  for a in ABC:
    return False
  return True

Cette variante utilise des générateurs pour représenter les résultats intermédiaires.

• Dans le générateur AB, nous aurons au plus n éléments (à cause de la garantie que les listes d’entrée ne contiendront pas de doublons), et produire le générateur prend une complexité de O (n²).
• La production du générateur ABCimplique une boucle sur le générateur ABde longueur n et Cde longueur n , de sorte que sa complexité algorithmique est également O (n²).
• Ces opérations ne sont pas imbriquées mais se déroulent indépendamment, de sorte que la complexité totale est O (n² + n²) = O (n²).

Étant donné que des paires de listes d'entrées peuvent être vérifiées séquentiellement, il s'ensuit que déterminer si un nombre quelconque de listes est disjoint peut être fait en un temps O (n²).

Cette analyse est imprécise car elle suppose que toutes les listes ont la même longueur. Nous pouvons dire plus précisément qui ABa au plus la longueur min (| A |, | B |) et le produire a la complexité O (| A | • | B |). Produire ABCa une complexité O (min (| A |, | B |) • | C |). La complexité totale dépend alors de la manière dont les listes d'entrées sont ordonnées. Avec | A | ≤ | B | ≤ | C | nous obtenons la pire complexité totale de O (| A | • | C |).

Notez que des gains d’efficacité sont possibles si les conteneurs d’entrée permettent des tests d’appartenance rapides au lieu de devoir répéter tous les éléments. Cela peut être le cas quand ils sont triés de manière à pouvoir effectuer une recherche binaire, ou quand ils sont des ensembles de hachage. Sans boucles imbriquées explicites, ceci ressemblerait à ceci:

for a in A:
  if a in B:  # might implicitly loop
    if a in C:  # might implicitly loop
      return False
return True

ou dans la version basée sur le générateur:

AB = (a for a in A if a in B)
ABC = (a for a in AB if a in C)
for a in ABC:
  return False
return True

Notez que si tous les éléments sont différents dans chacune des listes supposées, vous ne pouvez itérer C qu'une seule fois pour chaque élément de A (s'il existe un élément de B égal). Donc la boucle interne est O (n ^ 2) total

Nous supposerons qu'aucune séquence individuelle ne contient de doublon.

est une information très importante.

Sinon, le pire cas de version optimisée serait toujours O (n³), lorsque A et B sont égaux et contiennent un élément dupliqué n fois:

i = 0
def disjoint(A, B, C):
    global i
    for a in A:
        for b in B:
            if a == b:
                for c in C:
                    i+=1
                    print(i)
                    if a == c:
                        return False 
    return True 

print(disjoint([1] * 10, [1] * 10, [2] * 10))

qui produit:

...
...
...
993
994
995
996
997
998
999
1000
True

En résumé, les auteurs partent du principe que le pire cas O (n³) ne devrait pas arriver (pourquoi?) Et "prouvent" que le pire cas est maintenant O (n²).

L’optimisation réelle consisterait à utiliser des ensembles ou des dessins afin de tester l’inclusion dans O (1). Dans ce cas, disjointserait O (n) pour chaque entrée.

Pour mettre les choses dans les termes que votre livre utilise:

Je pense que vous n’avez aucun mal à comprendre que le chèque a == best O (n ² ) dans le cas le plus défavorable .

Dans le pire des cas pour la troisième boucle, chaque aentrée Aa une correspondance B, donc la troisième boucle sera appelée à chaque fois. Dans le cas où il an’existe pas C, il parcourra l’ Censemble.

En d’autres termes, c’est 1 fois pour chaque aet 1 fois pour chaque c, ou n * n. O (n ² )

Donc, il y a le O (n ² ) + O (n ² ) que votre livre indique.

Le truc de la méthode optimisée est de couper les coins ronds. Seulement si a et b correspondent, c sera regardé. Maintenant, vous pouvez imaginer que dans le pire des cas, vous devrez toujours évaluer chaque c. Ce n'est pas vrai.

Vous pensez probablement que le pire des cas est que chaque vérification pour a == b aboutit à un passage sur C, car chaque vérification pour a == b renvoie une correspondance. Mais cela n’est pas possible car les conditions sont contradictoires. Pour que cela fonctionne, vous aurez besoin d'un A et d'un B qui contiennent les mêmes valeurs. Elles peuvent être ordonnées différemment, mais chaque valeur de A devrait avoir une valeur correspondante de B.

Maintenant, voici le kicker. Il n’existe aucun moyen d’organiser ces valeurs, de sorte que pour chaque a, vous auriez à évaluer tous les b avant de trouver votre correspondance.

A: 1 2 3 4 5
B: 1 2 3 4 5

Cela se ferait instantanément car les 1 correspondants sont le premier élément des deux séries. Qu'en est-il de

A: 1 2 3 4 5
B: 5 4 3 2 1

Cela fonctionnerait pour le premier passage sur A: seul le dernier élément de B donnerait un succès. Mais la prochaine itération sur A devrait déjà être plus rapide car la dernière place de B est déjà occupée par 1. Et en effet, cela ne prendrait que quatre itérations cette fois. Et cela s'améliore un peu à chaque prochaine itération.

Maintenant, je ne suis pas mathématicien, donc je ne peux pas prouver que cela se retrouvera dans O (n2) mais je peux le sentir sur mes sabots.

A été déconcerté au début, mais la réponse d'Amon est vraiment utile. Je veux voir si je peux faire une version très concise:

Pour une valeur donnée adans Ala fonction compare aavec tous les possibles bdans B, et il le fait qu'une seule fois. Donc, pour une donnée donnée, ail effectue a == bexactement les ntemps.

Bne contient pas de doublons (aucune des listes n'en contient), donc pour une donnée, ail y aura au plus une correspondance. (C'est la clé). Lorsqu'il y a correspondance, asera comparée à toutes les possibilités c, ce qui signifie qu'elle a == cest exécutée exactement n fois. Où il n'y a pas de match, a == cne se produit pas du tout.

Donc, pour une donnée a, il y a soit des ncomparaisons, soit des 2ncomparaisons. Cela se produit pour tous a, le meilleur cas possible est (n²) et le pire est (2n²).

TLDR: chaque valeur de aest comparée à chaque valeur de bet à chaque valeur de c, mais pas à chaque combinaison de bet c. Les deux problèmes s'additionnent, mais ils ne se multiplient pas.

Pensez-y de cette façon, certains nombres peuvent figurer dans deux ou trois séquences, mais le cas moyen est que, pour chaque élément de l'ensemble A, une recherche exhaustive est effectuée dans b. Il est garanti que chaque élément de l'ensemble A sera itéré, mais impliquera que moins de la moitié des éléments de l'ensemble b seront itérés.

Lorsque les éléments de l'ensemble b sont réitérés, une itération se produit s'il existe une correspondance. cela signifie que le cas moyen de cette fonction disjointe est O (n2) mais que le pire des cas absolu pourrait être O (n3). Si le livre n'entre pas dans les détails, il vous donnerait probablement une réponse moyenne.