세트의 두 숫자가 nlgn에서 x와 같은지 확인하십시오

Question

직접 해결할 수 있기 때문에 해결책이 필요하지 않습니다. 내가 원하는 것은 네가 맞다는 것입니다. 아니면 옳지 않아요. 팁이나 제안이 뒤 따르지 않고 답을 이끌어 낼 수 있습니다.

질문 :

n 개의 정수와 다른 정수 X의 세트 S 주어진 합 정확하게 x는 S의 두 요소가 존재하는지 여부를 결정하고, 세타 (nlgn) - 시간 알고리즘을 설명. (알고리즘에 대한 소개, 2.3-7)

시도 :

첫 번째 세트가 정렬되어 있는지 여부를 문제가 나던 상태입니다. 나는 그것이 최악의 경우에서 theta (nlgn) 인 것처럼 그것을 병합 정렬을 사용하여 정렬했다고 생각했다.

그럼 난 괜찮아,이 유일한 세타 (nlgn) 수있는 유일한 방법은 내가 재귀 적으로 문제를 두 개로 나눈 경우입니다. 내 접근 방식은 우리 배열의 색인 i = 0에서 시작하여 x = i + k에 대해 필요한 k 값을 확인한 다음 k가 발견 될 때까지 이진 검색을 사용하여 문제를 반으로 분할합니다. 내가 x = i + k 인 k를 찾지 못했다면, 인덱스 i = 2에서 n-1까지 같은 과정을 계속할 것입니다. 이것은 theta (nlgn)의 결과가됩니다.

정수를 제거하면 배열을 정렬하고 k를 찾는 데 드는 총 시간이 theta (nlgn) + theta (nlgn) = theta (2nlg2n) = theta (nlgn)가됩니다.

Answer 1

예, 해결책이 정확합니다. 발견 된 요소 k에 동일한 색인 i이있는 경우를 처리하는 것을 잊지 마십시오.