Timsort가 데이터 패턴의 이점을 취하는 몇몇 경우에 대해 O (n log n) 경계를 깨는 것을 들었습니다. 어떻게 가능합니까? 누구든지 나를 자세히 설명 할 수 있습니까? 그것이 사실이라면 실제 데이터에는 데이터를 제외하고 어떤 패턴이 존재하기 때문에 Timsort는 빠른 정렬보다 항상 비교가 적을 것입니다.어떤 경우 Timsort가 O (n log n) 분류를 초과 할 수 있습니까?
비교 정렬을 위해 평균 케이스에 바인딩 된 O (n log n)을 깨기 위해 어떤 종류의 트릭을 사용할 수 있습니까?
의미에 따라 달라집니다. 평균 여기에 있습니다. CS 필드 내에서 평균은 매우 정확한 의미를 갖습니다. 각 가능한 입력 세트가 동일한 확률을 가진다고 가정 할 때 가능한 모든 입력 세트에 대한 평균입니다.이 정의는 정확하고 다루기 쉽기 때문에 편리합니다. 그러나 실제 단어 데이터가 일반적으로 난수와 다르므로 평균이 일 때 일 것입니다. 모든 실제 입력 세트에 대해을 의미합니다. 그러나 이것은 매우 정확하지 않으며 과학적 맥락에서 작동하지 않으므로 학계에서이 사실을 발견하지 못할 것입니다. 두 정의의 차이는 매우 크다. 실세계 데이터에서,고정 된 비율의 입력 집합이 있다는 것을 합리적으로 가정 할 수있다. 입력 집합은 timsort와 같은 것으로 선형 시간으로 정렬 될 수있다. 임의의 데이터의 경우 선형 시간으로 정렬 할 수있는 K2(n)의 백분율은 K2=Exp(-n)과 같이 매우 빠르게 0으로 바뀌고 입력 값의 크기는 n입니다. 따라서 질문에 대한 정확한 학문적 대답은 아니요입니다. 평균 사례는 개선 할 수 없습니다. 실제 엔지니어의 대답은 일 것입니다. 일 수도 있고, 시도해 볼 수도 있습니다. 그리고 그들은 그렇습니다.
http://en.wikipedia.org/wiki/Timsort –
임의 치환의 엔트로피는 n 로그 n입니다. 아니요, 평균적으로 더 잘할 수 없습니다. –
@Niklas이 정보는 단지 사용자의 의견입니다 거의 드문 경우가있는 기본 데이터에 대해 – pentadecagon