질문은 The Algorithm Design Manual의 질문입니다. 나는 그것에 대해 연구했지만 올바른 대답에 도달하는 방법을 찾지 못했습니다.배열의 고유 정수의 개수는 O (log n)입니다. 그런 시퀀스를 정렬하는 O (n log log n) 최악의 경우 시간 알고리즘을 얻는 방법?
질문 : 우리는 S에서 고유 한 정수의 수가 O (log n)가되도록 많은 중복을 갖는 n 개의 정수로 이루어진 시퀀스 S를 정렬하려고합니다. O (n log log n) 최악의 경우 시간 알고리즘을 사용하여 그러한 시퀀스를 정렬하십시오.
나는이 모든 별개의 요소들을 먼저 골라서 logn 길이의 배열을 만들고 주파수를 기록하고 정렬 할 수있을 것이라고 생각한다. 그러나 내 첫 번째 단계는 너무 많은 시간을 날려 버리는 것 같습니다 ... 어떤 우수한 선택 방법인가요, 아니면 완전히 잘못된 방법입니까? 감사합니다
각 번호의 발생 횟수를 계산하려면 균형 이진 트리를 사용하십시오. 로그 N 개의 고유 번호 만 있기 때문에 트리의 크기는 로그 N이므로 모든 작업은 로그 로그 N에서 수행됩니다 (정확히 <>가 구현 된 방법은 C++입니다)
그런 다음 선주문 순회 (pre-order traversal)에서 트리의 노드를 찾은 다음 각 정수를이 순서로 필요한 횟수만큼 인쇄합니다.
감사합니다. 하지만 O (nloglogn)보다 적은 시간을 사용하여 정렬되지 않은 배열에서 균형 잡힌 이진 트리를 생성하기위한 몇 가지 힌트를 제공 할 수 있습니까? – user4111965
물론 빈 균형 조정 된 이진 트리부터 시작하여 각 정수에 대해 다음을 수행하십시오. 1) 이미 트리에 있는지 확인하고, 트리에 있으면 카운터를 1 씩 증가시킵니다. 2) 그렇지 않으면 트리에 삽입하십시오. 각 작업은 O (로그 로그 N)이므로 O (N 로그 로그 N)입니까? – Irvan
(고유 숫자, 개수) 쌍을 포함하는 배열을 만듭니다. 배열은 처음에는 비어 있고 정렬 된 상태로 유지됩니다.
원래 배열의 각 번호에 대해 이진 검색을 사용하여 정렬 된 배열의 번호를 확인하십시오. 배열은 크기가 O (log N)이기 때문에, 매번 바이너리 검색은 O (로그 로그 N)을 취하고, N 번, 총 O (N 로그 로그 N)을 수행합니다. 발견되면 카운트를 증가시킵니다.
숫자가 1 인 새 번호를 삽입합니다.이 작업은 O (로그 N) 번만 발생하며 O (로그 N) 단계에서 수행되므로 총 O 2 N)이며 이는 O (N log log N)보다 훨씬 작습니다.
끝나면 원래 배열에 필요한 번호를 채 웁니다. 그건 O (N)가 걸립니다.
고유 번호 집합이 너무 작기 때문에 삽입을 더 빠르게 수행 할 균형 정렬 된 트리를 만들 필요가 없습니다.
정수 집합이 모두 X ≤ number ≤ Y 범위에 포함되면 X - Y + 1 배열을 사용하여 O (max (N, Y - X + 1))에서 문제를 해결할 수 있습니다. 카운터와 고유 한 번호를 찾는 것을 괴롭히지 않습니다. 이 기술은 이안 뱅크 (Iain Banks)의 책 "Player of Games"에 큰 영향을 준 것으로 보도되었다.
"나는이 모든 별개의 요소를 먼저 선택하여 logn 길이의 배열을 만들고 주파수를 기록하고 정렬 할 수 있다고 생각합니다." 아마도 데이터 구조의 선택을 제외하고 나에게 합리적이라고 생각합니다. "그러나 내 첫 발걸음은 너무 많은 시간을 날려 버리는 것 같다."너 설명 할 수 있니? –
시퀀스 S에서 중복되는 정보가 있습니까? 왜 당신은 O (log n) 개의 별개의 정수를 S로 가정 할 수 있습니까 ?? S에서 n 개의 고유 정수가 가능할 수 있습니다. –
*** X ***는 고유 한 정수의 수이고, * log n *이됩니다. 그런 다음 문제는 *** O (n log X) ***에 정렬되는 알고리즘을 요구합니다. 문제를 해결 한 후 *** X ***을 *** log n ***로 바꾸십시오. – jww