다음은 몇 가지 임의의 아이디어입니다.

• 동적 프로그래밍 알고리즘을 뒤집어 가장 큰 합계 대신 가장 작은 합계를 찾을 수 있습니다. 당신은 하나의 합동에 0 대신에, 전체 배열의 나머지에 합한 합을 찾는다. 요소를 오름차순으로 처리하면 전체 배열을 처리하기 전에 동적 알고리즘이 종료 될 수 있습니다.

  k 개의 요소를 처리하면 비용은 입니다. 있다 없다 의 하한 Ω ( N 로그 N ) 우리는 모든 요소를 정렬 할 필요가 없기 때문에이 알고리즘에. k 개의 가장 작은 요소 를 얻는 데 O ( n log k ) 시간 만 걸립니다 .O(nk)

  $O(nk)$

  $O(n k)$k

  $k$

  $k$Ω(nlogn)

  $\mathrm{\Omega }(n\log n)$

  $\Omega(n \log n)$O(nlogk)

  $O(n\log k)$

  $O(n \log k)$k

  $k$

  $k$

• 가장 큰 크기의 집합 대신 큰 크기의 집합을 염두에두면 빠른 푸리에 변환 기반 다항식 곱셈을 사용하여 시간. 도메인 범위가 제한 될 때 3SUM 에서 수행 한 것과 유사합니다 . (참고 : 사용은 다른 당신이 얻을 것이다, 이진 검색을 할 제곱 반복 O ( N K ( 로그 N ) ( 로그 로그 N ) ) KO(n(logn)2(loglogn))

  $O(n(\log n{)}^2(\log \log n))$

  $O(n (\log n)^2 (\log \log n))$O(nk(logn)(loglogn))

  $O(nk(\log n)(\log \log n))$

  $O(n k (\log n) (\log \log n))$k

  $k$

  $k$ 생략 된 요소의 수입니다.)

• 때 복합이며, 거의 모든 나머지 중 하나의 배수이다 N 의 요인 상당한 시간이 그 요소의 배수가 아닌 나머지에 초점을 맞춤으로써 저장 될 수 있습니다.n

  $n$

  $n$n

  $n$

  $n$

• 잔차 r가 매우 흔하거나 잔재가 거의없는 경우 ‘여기에서 시작하면 다음 열린 슬롯을 추적하고 r정보를 계속 사용하여 정보를 계속 유지 ‘하면 많은 점프 스캔 대 오픈 스팟을 저장할 수 있습니다. 시각.

• 도달 가능성 만 추적하고 플립 된 동적 알고리즘에서 비트 마스크를 사용한 다음 대상 나머지에 도달하면 역 추적 하여 로그 요소 를 면도 할 수 있습니다 .

• 동적 프로그래밍 알고리즘은 병렬로 실행될 수 있습니다. 각 버퍼 슬롯에 대한 프로세서를 사용하면 까지 내려갈 수 있습니다 . 또는 O ( n 2 ) 폭을 사용하고 반복 집계 대신 집계를 분할 및 정복함으로써 회로 깊이 비용을 O ( log 2 n ) 까지 줄일 수 있습니다 .O(n)

  $O(n)$

  $O(n)$O(n2)

  $O(n^2)$

  $O(n^2)$O(log2n)

  $O({\log }^{2}n)$

  $O(\log^2 n)$

• (메타) 나는 당신이 겪은 문제가 연속적인 합 에 관한 것이라고 강력히 의심합니다 . 실제 문제와 연결되어 있으면 쉽게 확인할 수 있습니다. 그렇지 않으면이 문제가 “알고리즘 소개”라는 과정에서 배정 된 것을 감안할 때이 문제가 얼마나 어려운지 매우 놀랐습니다. 그러나 어쩌면 당신은 그것을 사소하게 만드는 트릭을 다루었습니다.

답변