는, 예를 들어, 세타 (nlogn)

Question

나는 이번 학기 알고리즘을 과정을 촬영하고 난을 설명

2.3-7 CLRS

의 문제를 해결하기 위해 노력하고 theta (ng n) 시간 알고리즘은 n 개의 정수로 이루어진 집합 S와 정수 x가있는 경우 S에 합계가 x 인 두 개의 요소가 있는지 여부를 결정합니다.

이 문제를 해결하는 방법을 모릅니다. nlogn 시간에 완료되기 때문에 병합 정렬 알고리즘을 사용하여 해결하기 위해 노력하고 있지만 올바른 접근 방법인지 잘 모릅니다.

실행 시간이 이미 지정된 경우 알고리즘을 해결할 때 일반적인 방법은 무엇입니까?

감사합니다.

Answer 1

"알고리즘 제안"작업에서와 같이 이러한 문제에 대한 일반적인 접근법은 의심 스럽습니다. 그러나 필요한 런타임은 "구성 요소"(일반적으로 log의 존재는 트리 또는 정렬 된 배열의 필요성을 나타냄)를 사용할 수 있음을 암시 할 수 있습니다. 예를 들어, 각 필수 런타임의 알고리즘 예는 tag wiki for 'big-o'을 참조하십시오.

문제에 대한 알고리즘의 아이디어 :

첫째, 일종의 배열 (O(n lg n)); 그런 다음 배열의 각 요소 y에 대해 x-y 요소가 있는지 확인합니다 (배열이 정렬되었으므로 O(n lg n) 임).