Discussion :

[Ja Rasta]

Bonjour à tous.

J'ai 2 fonctions python identiques dans la forme mais différentes dans le fond.

Première fonction :
Ici il s’agit de la première variante de 2SUM : on cherche si deux éléments de T somment à −z.
Complexité : O(n²)

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
def 3SUM(T):
  T.sort()
  for z in T:
    if 2SUM(T,-z):
       return True
  return False

2ème fonction :
Attention : On n’a pas réduit 3SUM à 2SUM car on appelle 2SUM un nombre non borné de fois.

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
def 3SUM(T):
   T.sort()
   for z in T:
      if 2SUM(T,-z):
          return True
   return False

J'arrive vraiment pas à voir d'où vient la différence puisque pour moi si l'appel à 2SUM est non borné dans la 2ème Fonction alors il l'est aussi dans la 1ère mais pourquoi on ne soulève pas cette inquiétude dans la 1ère fonction?
Si quelqu'un voit la différence merci de m'aider à la voir.

[anapurna]

salut

dans les deux cas ta fonction est borné
tu parcourt T
dans les deux cas dés que l’occurrence est vrai tu sort de ta boucle
au vu du code que tu nous as fournis les deux fonctions sont identique

[Ja Rasta]

Merci.