Wie kann man einen besseren Algorithmus mit diesem Code erstellen?

Question

Ich habe dieses algo und ich möchte wissen, ob es möglich ist, um es besser zu machen (weniger Komplexität):

for i = 3 to A.length 
    for j = 2 to i − 1 
    for k = 1 to j − 1 
     if |A[i] − A[j]| = = |A[j] − A[k]| or |A[i] − A[k]| = = |A[j] − A[k]| 
      return true 
return false 

Die Komplexität O sein muss (n^3), und der Satz nach „oder“ ist nur A [i] = A [j]

ich bin nicht sicher, dass ein besseren Algorithmus existieren könnte ...

Answer 1

Sie zu O(n^2) Zeit verringern könnten (aber erhöht Raum Komplexität) von den Grafen von Differenzen Hashing .

Answer 2

Sie können das Array sortieren vorher und Binär-Suche, um die Zeitkomplexität von O (N^3) zu O (N^2 logN) zu Fall zu bringen.

Pseudo-Code -

sort(A) 

for i = 1 to A.length - 2 
    for j = i + 1 to A.length - 1 
     //search for an element A[k] such that A[k]-A[j] == A[j]-A[i] 
     if binary_search(A, 2 * A[j] - A[i], j + 1, A.length) 
      return True 
return False 

binary_search(A, x, i, j) kehrt true wenn x ist in A zwischen Indizes i und j.

Im Gegensatz zu den anderen Lösungen mit Hashing benötigen Sie keinen zusätzlichen Speicherplatz.