Как сделать лучший алгоритм с учетом этого кода?

Question

у меня есть этот Algo и я хочу знать, если это возможно, чтобы сделать его лучше (меньше сложности):

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 

Сложность должна быть O (N^3), и приговор после того, как «или» является просто A [я] = A [J]

Я не уверен, что может существовать лучший алгоритм ...

Answer 1

Вы могли бы свести к O(n^2) времени (но увеличение пространства сложности) путем хеширования отсчетов различий ,

Answer 2

Вы можете отсортировать массив заранее и использовать бинарный-поиск, чтобы сбить сложность времени от O (N^3) к O (N^2) LogN.

Псевдокод -

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) возвращает true если x присутствует в A между показателями i и j.

В отличие от другого решения, связанного с хешированием, вам не понадобится дополнительное пространство.