이 코드가 주어질 때 더 나은 알고리즘을 만드는 방법은 무엇입니까?

Question

나는이 너 한테이 있고 그것이 더 나은 (덜 복잡) 할 수 있다면 내가 알고 싶은 :

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는 [I] = A [J]

나는 그것이 더 나은 알고리즘을 존재할 수 모르겠습니다 ...

Answer 1

당신은 차이의 수를 해싱에 의해 O(n^2) 시간 (그러나 증가 공간의 복잡성)을 감소시킬 수있다 .

Answer 2

당신은 배열을 미리 정렬 O (N^2 logN)에 O (N^3)에서 시간 복잡도를 가지고 이진 검색을 사용할 수있다.

의사 코드 -

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) 복귀 truex 경우 인덱스 i 및 jA 사이에 존재한다.

해싱이 포함 된 다른 솔루션과 달리 추가 공간이 필요하지 않습니다.