Discussion :

[greenHor]

Bonjour,
Mon but est d'améliorer la complexité de ma solution au problème suivant :
On a un tableau d'entiers t = [t1 < t2 ... < tn]. Le but est de compter le nombre de triplets ti , tk , tj tels que tk - ti = tj - tk.
Ma solution s'exécute en O(n²) (en Python):

s = 0
for k in range(1, n-2):

i,j = k-1, k+1

temp = 2 * t[k]

while i >= 0 and j < n:

if t[i] + t[j] == temp:

s+=1

i-=1

j+=1

elif t[i] + t[j] < temp:

j+=1

else:

i-=1

Par exemple, [1,3,4,5] va donner s = 2.

Y a-t-il une solution plus efficace ?
Merci

[wiwaxia]

Bonjour,

L'idée de partir de (k), puis d'élargir les bornes (i, j) est inattendue.
J'ai pratiqué un peu le Python, et la lecture de ton programme - pour autant que je l'ai bien compris - appelle deux remarques:
a) (k) ne varie-t-il pas entre (2) et (n - 1), puisqu'il est strictement compris entre (i) et (j), donc entre (1) et (n) ?

Code :

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

1
2
 ... On a un tableau d'entiers t = [t1 < t2 ... < tn] ... 
for k in range(1, n-2):

b) Le programme fonctionne-t-il correctement sur des listes très dissymétriques, par exemple:
t = (1, 4, 9, 16, 25, 36, 41, 49, 64, 81, 100) ?

La suite étant ordonnée, je serais spontanément parti des indices extrêmes; tu traduiras facilement ce qui suit:

Code :

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

1
2
3
4
5
6
7
8
9
FOR k:= 1 TO n DO u[k]:= 2 * t (k );
s:= 0;
FOR i:= 1 TO (n - 2) DO
  FOR j:= (i + 2) TO n DO
    BEGIN
      a:= t[i] + t[j]; 
      FOR k:= (i + 1) TO (j -1) DO
        IF (u[k]=a) THEN Inc(s)
 ...

Le calcul des valeurs doubles est consigné une fois pour toutes dans un second tableau (u) isotype de (t).
La complexité n'est sans doute pas diminuée, mais les calculs un peu plus rapides sur une plus longue liste.

[greenHor]

Merci de ta réponse
Effectivement, en fait t = [t0 < t1 ... < t(n-1)]
Donc le n-2 devient n-1 (le range va aller de 1 à n-2)

Ensuite, je pense qu'il fonctionne : pour le prouver, on peut d'abord dire que un élément "milieu" est forcément entre 1 et n-2:
-si tk-1 et tk+1 marchent, alors on incrémente s (premier cas) et on sais que tk-1 ne marchera avec rien d'autre (puisque les éléments sont distincts et triés) et c'est la même chose pour tk+1 -si tk-1 + tk+1 < 2*tk, alors on sais que tk+1 ne marchera avec rien à gauche de tk (puisque tout les ti avec i<k-1 sont plus petits que tk-1)
-on a la même chose pour le cas >

Merci pour ta proposition : à première vue elle est en n^3, mais je vois comment la passer en n².

[tbc92]

J'ai l'impression que la solution de Wiwaxia est beaucoup plus lente que la solution proposée par GreenHor.

La solution de GreenHor me paraît quasiment optimisée. On doit quand même pouvoir faire mieux en passant par des dictionnaires. Si on reprend les données de Wiwaxia, on va inverser le stockage, en disant Dico[1] = 1,Dico[4] = 2,Dico[9]=3 etc ...
Ainsi quand on a calculé 2*t[k] - t[i], on peut déterminer immédiatement si il existe un j tel que t[j] = 2*t[k]-t[i], plutôt que passer par une boucle. Mais par rapport à la solution de GreenHor, le bénéfice me paraît minime.

Si on veut,on doit aussi pouvoir stocker d'une part les t[i] impairs, et d'autre part les t[i] pairs... et ainsi, pouvoir aller plus vite. Si t[i] + t[j] = 2*t[k], forcément t[i] et t[k] sont de même parité. Mais le bénéfice paraît minime.

[greenHor]

Merci !
n² est vraiment trop pour moi, alors je pense que mon vrai problème (duquel découle celui-ci) a une solution plus rapide qui n'utilise pas cette simplification.

[tbc92]

Et par curiosité, n est de quel ordre de grandeur, et aussi, les t[k] sont de quel ordre de grandeur ?

[greenHor]

Les deux sont de l'ordre du million, et j'ai une seconde pour tout faire