스트리밍 된 데이터를 정렬 된 목록으로 읽기

Question

일반적으로 최악의 경우의 복잡도 O (N * log (N))에서 실행되는 임의의 데이터에 대해 "더 똑똑한"비교 정렬을 수행합니다.

제 질문은 컬렉션을 정렬하지 말고 데이터 스트림을 요청하면 어떻게됩니까? 즉, 값은 우리에게 다음에 오는 것의 표시 자없이 하나씩 주어집니다 (데이터가 유효/범위 내에 있음을 제외하고). 직관적으로, 모든 것을 모으고 나중에 정렬 (포커 핸드를 처리 한 후 정렬)보다는 오히려 그것이 나오는대로 데이터를 정렬하는 것이 더 우수하다고 생각할 수도 있습니다 (하나씩 포커 핸드를 선택하는 것). 이게 사실인가요?

수집 및 정렬은 O (N + N * log (N)) = O (N * log (N))이됩니다. 그러나 그것이 오면 정렬 할 때, 그것은 O (N * K)입니다. 여기서 K = 적절한 색인 + 요소를 삽입 할 시간을 찾는 시간입니다. K의 가치는 이제 데이터 구조의 선택에 달려 있기 때문에 이것은 복잡합니다. 배열은 인덱스를 찾는 것이 우수하지만 요소를 삽입하는 데 시간을 낭비합니다. 연결된 목록은 더 쉽게 삽입 할 수 있지만 이진 검색으로는 색인을 찾을 수 없습니다.

이 문제에 대한 전체적인 논의가 있습니까? 우리는 언제 다른 방법을 사용해야합니까? 때때로 서로를 소팅하는 바람직한 중간 전략이있을 수 있습니까?

Answer 1

Balanced tree sort은 O(N log N)이고 요소가 추가되는 동안 정렬 된 순서로 목록을 유지합니다.

Answer 2

절대적으로!

우선 스트리밍 데이터를 정렬 할 수 있다면 모든 데이터를 O(N)에 수신 한 다음 직접 스트리밍하여 빠른 방법으로 정렬 할 수 있습니다. 나는. 모든 데이터에서 스트림으로 축소를 수행 할 수 있으므로 더 빠를 수 없습니다.

둘째, 당신이 실제로 O(N^2) 시간에 실행되는 삽입 정렬을 설명하고 (예 : O(NK) 당신의 설명을 잘했지만, K는 N 오히려 기능 일정하지)가 발견 O(N) 시간이 걸릴 수 있기 때문에, 적절한 색인. 이를 바이너리 삽입 정렬로 개선 할 수는 있지만(링크 된 목록을 사용한다고 가정하면 배열은 여전히 ​​이진 최적화에서도 O(N^2)이됩니다), 실제로 아무 것도 저장하지 않았습니다.

아마도 일반적인 원칙을 언급 할 가치가 있습니다. 비교 모델을 사용하는 한 (즉, 정렬하려는 데이터에 대해 중요하지 않은 유용한 정보가없는 경우) 정렬 알고리즘은 모두 O(NlogN) 일 것입니다. 나는. 이 모델에서 정렬 알고리즘의 최악의 실행 시간은 omega(NlogN)입니다. 그것은 가설이 아니라 정리입니다. 따라서 더 빠른 것을 찾는 것은 불가능합니다 (동일한 가정 하에서).

Answer 3

좋아, 스트림의 타이밍이 비교적 느린 경우 마지막 요소가 도착하면 완전히 정렬 된 목록 (마지막 요소 빼기)이 표시됩니다. 그런 다음 O (log n) 이진 정렬이 아닌 단일 이진 검색주기 O (n log n)입니다. 잠재적으로, 다른 정렬 알고리즘에서 앞서 가고 있기 때문에 성능이 크게 향상됩니다.

스트림에서 데이터를 관리, 큐 및 추출하는 것은 완전히 다른 문제이며 사용자의 의도에 대해 역효과를 줄 수 있습니다. 하나 또는 두 개의 요소를 스트리밍하는 것과 거의 같은 시간에 전체 데이터 세트를 정렬 할 수 있고 스트리밍 부분을 코딩하는 것이 좋다고 생각하지 않는 한이 방법을 권장하지 않습니다.

Answer 4

트리 정렬에 트리 구조를 저장하기위한 추가 공간이 필요하므로 트리 정렬, 즉 대용량 데이터 세트가 작동하는 경우 힙 정렬을 사용하십시오.