이것은 숙제 문제 였지만 강사가 솔루션을 설명하고 내가 아직 이해할 수없는 강의를 놓쳤습니다 ...인접한 차이의 합이 2보다 작은 숫자의 순열을 제공하는 알고리즘.
간격 [0,1] (즉, x1, x2, x3, ..., xn)에 n 개의 실수가 주어지면 최악의 선형 시간에서 순열을 수행하는 알고리즘이 있음을 보여줍니다 이 n 개의 숫자 중 인접한 숫자의 차이의 합이 2보다 작아야합니다. 주어진 힌트는 "버킷"입니다.
글쎄, 이렇게 갈 수 있습니다. [0, 1]을 k 세그먼트 : [0, 1/k), [1/k, 2/k), ..., [(k-1)/k, 1]으로 분할하십시오.
이제는 목록을 살펴보고 첫 번째 세그먼트에 들어 맞는 숫자보다 먼저 새 목록을 넣으십시오. 한 번에 완료 할 수 있으므로 O(n)입니다.
지금 필요한 합계를 고려하십시오. 동일한 세그먼트 내의 숫자의 차는 최대로 1/k이고, 이러한 차이의 수는 n-(k-1)입니다. 나머지 (n-1) 개의 diff는 인접한 버킷의 숫자 사이에 있으며 모두 1 이하 여야합니다. 합계는 (n-k+1)/k + (k-1)/k입니다. k만큼 충분히 작 으면 크게 만들 수 있습니다.
자세한 내용 :
가의 2 개 색상으로 우리의 차이를 페인트하자 같은 세그먼트에서 숫자 사이에 차이가 파란색 페인트, 그리고 다른 세그먼트에서 숫자 사이에 차이가 빨간색으로 칠해진다. 주문 덕분에 첫 번째 세그먼트의 숫자 만 가능하고 (0 일 수도 있음) 두 번째 세그먼트의 숫자보다 많습니다. 그래서, 우리는 첫 번째 파란색 차이가 있습니다, 다시 빨간 차이 등보다 몇 가지 파란색 차이보다 붉은 차이가 있습니다.
빨간 차이의 수를 봅시다. 분명히 k-1 붉은 차이가 있지 않습니까? 각 빨간색 차이가 한 세그먼트에서 상위 세그먼트로 이동하기 때문입니다. 차이점의 나머지 부분은 파란색입니다.
이제 파란 차이는 1/k보다 크지 않습니다. 왜냐하면 피감수 및 감수가 동일한 세그먼트에서 발생하기 때문입니다. 그리고 모두 모든 빨간색의 차이 (즉, 자신의 합이다!) (이 숙제 질문으로, 지금은 나머지를 건너 뜁니다.) 1. 초과하지 않는
수정 :
모든 빨간색의 합 차이는 2-2/k를 초과하지 않습니다. 왜 그런가요? 어디 한번 보자.첫 번째 빨간색 차이는 일부 세그먼트 A의 시작부터 다른 세그먼트 B의 끝까지 최악의 경우 일 수 있습니다. 두 번째는 부터까지 B부터 다른 세그먼트 C 끝까지 최악의 경우입니다. 따라서 차이의 합계에서 첫 번째와 마지막을 제외한 모든 세그먼트는 최대 두 번 계산됩니다.
간격을 같은 길이로 나누어보십시오. 이제는 임의의 순서로 속한 간격에 숫자를 넣고 이것이 문제를 해결했음을 증명하십시오.
버킷 종류에 대해 배웠습니까? {0, .5, .75은, 1} : http://en.wikipedia.org/wiki/Bucket_sort
또한 정렬 된 배열의 동작을 살펴 차이의 합이 1
비교하다 정렬되지 않은 배열의 행동 : { .75, .5, 0, 1} : 차이의 합은 1.75
위대한 설명 :) – Adrian
@ 애드리안 : 감사합니다! – Vlad
답변 해 주셔서 감사합니다! 그러나 나는 아직도 이것의 일부를 이해하지 못한다. (n- (k-1)과 같은 숫자를 얻는 방법에 대해 좀 더 자세히 설명해 주시겠습니까? 또한 같은 세그먼트에있는 숫자들의 diffs 1/k 미만이어야합니다. – tom