Two-Sum-사전 정렬 최적화 알고리즘 설계

Nov 23 2020

🧩 오름차순 또는 내림차순으로 사전 정렬 된 입력을 수신하여 2- 합 솔루션의 런타임을 최적화 할 수 있습니까?

🚀 오리지널 Two-Sum

동일한 항목을 두 번 선택할 수 없도록 개별 용량이 총 용량과 완벽하게 동일한 두 항목이 있는지 확인합니다.

  • 입력 : 총 용량을 나타내는 Int와 항목의 개별 용량을 나타내는 Int의 배열.
  • 출력 : 두 항목이 총 용량과 같을 수 있는지 여부를 나타내는 부울입니다.
  • 시간 복잡성 : 선형 성장, $O(n)$
  • 공간 복잡성 : 선형 성장, $O(n)$

견본

입력: [4, 5, 2, 6]

  • 총 용량 : 10
  • 배고 있다: true

입력: [4, 5, 2, 5]

  • 총 용량 : 10
  • 배고 있다: true

입력: [4, 5, 2, 7]

  • 총 용량 : 10
  • 배고 있다: false

의사 코드

  1. searchSet이미 검사 한 항목을 저장할 세트 를 만듭니다 .

  2. 항목 용량의 입력 배열을 반복합니다.

    2a. targetCapacity현재 항목 찾기 :totalCapacity - itemCapacity

    2b. 를 searchSet포함하는 targetCapacity경우를 반환 true합니다.

    2c. 그렇지는 추가 itemCapacity받는 사람 searchSet.

  3. false일치하는 항목을 찾지 않고 전체 입력이 반복되는 경우 반환 합니다.

🏗️ 사전 정렬

  1. 새 변수 저장 lastTargetCapacity
  2. 현재 itemCapacity< lastTargetCapacity이면 가능한 두 합계 및 반환이 없습니다 false.

입력: [6,2,1,0]

  • 총 용량 : 9

반복

  1. targetCapacity = 9 - 6, lastTargetCapacity= 3
  2. 때문에 거짓 반환 itemCapacity2< lastTargetCapacity3.

답변

AdamHurwitz Nov 28 2020 at 23:41

Two Sum 솔루션은 입력 배열이 오름차순 또는 내림차순으로 미리 정렬되어 있으므로 런타임 성능을 위해 최적화 할 수 있습니다.

이진 검색을 사용하여 targetCapacity위 를 찾으면 로그로 실행되며,$O(logn)$, 평균 런타임. 이것은 선형으로 실행되는 위의 의사 코드보다 빠릅니다.$O(n)$, 반복 및 해싱을 사용하는 런타임.

입력에 정렬이 제공되지 않으면 다음보다 빠르게 정렬 및 검색 할 수 없습니다. $O(n)$. 할 수있는 최선은$O(nlogn)$ Quicksort 및 Binary Search와 같은 전략을 사용합니다.

참조 : Stanford-Two Sum 설명

D.W. Nov 30 2020 at 12:46

예, 다음에서 2 합 문제를 해결할 수 있습니다. $O(n)$시간, 숫자가 정렬 된 순서로 표시되는 경우. 방법은 다른 답변 을 참조하십시오 . 선형 스캔이 포함됩니다. 이미 소요되므로 점근 적으로 최적입니다.$O(n)$ 입력을 읽는 데에도 시간이 걸리고 문제를 해결하려면 전체 입력을 읽어야 할 수 있으므로 점근 적 개선이 더 이상 없습니다.