입력은 실수 x1, x2, ..., x2n의 시퀀스입니다. 이 수를 n 쌍으로 쌍으로 만듭니다. i 번째 쌍 (i = 1, 2, ..., n)에 대해 Si는 그 쌍의 숫자의 합을 나타냅니다. (예를 들어, x (2i-1)과 x2i를 i 번째 쌍으로하면, Si = x (2i-1) + x2i). 우리는 Maxi [Si]가 최소화되도록이 수를 짝지기를 원합니다. 이 문제를 해결하기위한 욕심 많은 알고리즘을 설계하십시오.최대 합을 최소화하는 숫자를 쌍으로 만드는 욕심 많은 알고리즘
그건 질문입니다. 내 솔루션은 간단하게 숫자를 정렬하고 첫 번째 요소와 add-one/subtract-one 색인을 쌍으로 만들고 반복하는 것입니다. 알고리즘은 각 쌍을 최적화하려고 시도하므로 욕심을 먹습니다. 이 작업을 수행 할 선형 시간 알고리즘이 있는지 궁금합니다.
추신 : 이것은 숙제는 아니지만,이 점이 매우 비슷하다는 것을 이해합니다.
아니요.이 작업을 수행하는 데 선형 시간이 필요하지 않습니다. 입력 된 숫자는 어떤 순서로도 될 수 있으므로 최소 Maxi [Si]로 페어링을 바로 할 수는 없습니다. 현재의 솔루션은 간단하고 좋습니다.
제안은 실행 시간을 개선하기 위해 :
당신은 입력 번호에서 이진 트리를 만들 수 있습니다 (이 (nlog (N)) 시간 O 소요). 트리의 inorder 순회를 수행하고 (first + i, last-i) 요소 (0에서 n/2까지)로 쌍을 만듭니다.
확인해 주셔서 감사합니다! – user183037
실행 시간에 따라 이진 트리가 어떻게 향상됩니까? O (nlgn)에서 실행되는 정렬 방법을 사용하는 것과 다른 점은 무엇입니까? – user183037
O (nlgn)의 정렬 알고리즘을 사용하면 이진 트리와 동일한 순서가됩니다. –
욕심 많고 근사하기를 원한다면, 데이터의 고정 된 크기의 창을 한 번 실행하고 창 안의 쌍 번호 (창 왼쪽에있는 것과 다른 창에있는 쌍 번호 만)를 실행할 수 있습니다 - 왼쪽 끝이 아닌 것을 표시하여 다시 사용하지 않고 왼쪽 끝의 창을 다시 사용하지 않도록 창을 앞으로 이동하십시오. 이것은 지역적으로 만 최적이라는 의미에서 욕심이 많습니다. 리스트가 일정하게 랜덤하다는 것을 안다면, 일정한 길이의리스트를 정렬하는 것이 N에 비례하여 일정한 시간이기 때문에 선형에 가까워 질 수 있습니다.리스트의 분포에 관한 다른 지식을 가지고 있다면, 여전히 O (N)이며 근사치입니다.
나는 근사가 문제가 말하는 것으로부터 괜찮다고 생각하지 않는다. 그래서 N을 정렬하는 것이 유일한 탈출구인가? – user183037
답변은 지금 삭제되었지만 게시했습니다 : 여기 [link ] (http://stackoverflow.com/questions/8970747/regarding-complexity-if-comparison-based-sorting-algorithm-used) * 임의의 요소 *에 대한 비교 기반의 정렬 기준에 관심이있는 모든 사용자를위한 것입니다. – cctan
나는 그곳에서 무슨 일이 일어 났는지 모른다. 내 대답과 함께 해답이 사라진 것 같다. 링크를 주셔서 감사합니다, 나는 임의의 요소에 대한 비교 기반의 정렬이 nlgn의 하한을 가지고 있다는 것을 알고 있습니다. 내가 궁금해하는 점은 두 숫자의 쌍을 선형으로 연결하여 합이 최소가되도록하는 것입니다. 나는 당신이 말하려고하는 것은 그것을 취하지 않고 다른 방법이 없다는 것입니다. 정렬과 소팅은 nlgn의 하한이 있습니까? – user183037
해결책이 정확합니다. 숫자를 정렬하고 처음과 마지막으로 반복적으로 페어링하십시오. 원한다면 증거를 제공 할 수 있습니다. – ElKamina