assignment: two-sum

[sonic247897]

O(n^2) 보다 낮은 시간 복잡도로 풀려면?

1. CS 배경지식

   • 배열은 메모리상 1차원 연속 공간에 저장됨
   • 배열 정렬 알고리즘 중에 가장 낮은 시간 복잡도를 가지는 병합정렬이나 힙정렬은 O(nlogn) 복잡도를 가진다.
   • 정렬된 배열에 대해서 탐색하는 알고리즘 중에 가장 낮은 시간 복잡도를 가진 이진 탐색 알고리즘은 O(logn) 복잡도를 가진다.

2. 수학적으로는 target보다 더 큰 원소들에 대해서는 탐색할 필요가 없다.

=> 위 두 가지 사실을 이용해서 1) {원소, index} 쌍을 저장하는 자료구조를 만들고, 2) 원소를 기준으로 오름차순으로 O(nlogn) 복잡도로 정렬한 다음, 3) 정렬된 배열에 대해서 이진 탐색으로 target보다 큰 원소는 탐색 범위에서 제외함.

그런데 이진 탐색 알고리즘으로 two sum을 찾을수 있나?? 복잡도만 기억나서 더 이상 분석이 어렵다.