각 알고리즘을 독립적으로 분석하고 선형 시간으로 어떤 알고리즘을 실행할 것인지 결정할 수 있는지 알아 봅시다.
먼저 계산 방식을 살펴 보겠습니다. 알고리즘은 다음과 같이 작동합니다.
- 정렬 할 최대 정수를 찾습니다.
- 정렬 할 정수 당 하나의 슬롯이있는 배열을 만듭니다.
- 주 배열을 반복하여 각 요소의 빈도로 두 번째 배열을 업데이트합니다.
- 출력 배열에 각 요소의 적절한 수를 채워서 정렬 된 배열을 구성합니다.
첫 번째 단계는 O (n) 시간에 메인 어레이를 반복하여 수행 할 수 있습니다. 배열의 최대 값이 U라고 가정합시다.이 경우, 2 단계는 O (U)를 취합니다. 배열 요소를 제로로해야하기 때문입니다. 세 번째 단계는 O (n) 시간이 걸립니다. 마지막 단계는 주파수 배열의 각 요소를 정확히 한 번 (O (U)) 방문하고 출력 배열 O (n)에 총 n 개의 쓰기를 만들기 때문에 시간 O (n + U)를 취합니다. 즉, 총 런타임은 O (n + U)입니다. 이것은 정렬해야하는 요소의 총 수 (큰 배열은 정렬하는 데 더 오랜 시간이 걸립니다)와 배열의 요소 크기에 따라 달라집니다 (더 큰 수는 비례하여 더 많은 런타임이 필요합니다).
이 런타임을 O (n)으로 만들려면 U = O (n)을 요구해야합니다. 그러면 O (n + U) = O (n + n) = O (n)이됩니다. 즉, 배열의 가장 큰 요소의 크기를 배열의 길이가 증가하는 것과 거의 같은 속도로 증가시킬 필요가 있음을 의미합니다. 예를 들어 배열의 모든 요소가 1 .. n 범위에 있음을 보장한다면 sort 계산에는 O (n) 시간이 걸립니다. 이러한 요소가 그 범위 내에서 어떻게 분포되어 있느냐는 중요하지 않습니다.
기수 정렬은 본질적으로 정렬 할 배열의 각 자릿수에 대해 반복적으로 계산 정렬을 반복하여 수행합니다.기수 정렬의 핵심 아이디어는 이전 알고리즘의 U 값을 가능한 한 낮게 유지하는 것입니다. 고정 된 기초를 선택하면 U의 값에 일정한 상수가 적용됩니다. 예를 들어, 2 진 기수 정렬을 사용하여 한 번에 한 비트 씩 이동하는 경우 정렬 할 배열의 각 요소는 본질적으로 0 또는 1로 처리됩니다. 즉 기수 정렬의 각 라운드에 시간이 필요합니다 (n)을 완료하십시오. 전체 배열을 정렬하는 데 필요한 라운드 수는 배열의 가장 큰 숫자 인 Θ (로그 U)의 자릿수로 지정됩니다. 즉, 알고리즘의 총 런타임은 O (n log U)가됩니다. 런타임은 요소의 수와 배열의 가장 큰 요소의 크기에 따라 달라집니다.
즉 U 로그 이번에는, 예를 들어 훨씬 더 느리게보다 U. 성장 이점 2 300는 전체 우주 원자 수 있지만, LG (2 300) = 약 300 인 그것은 아주 작습니다.
어떤 사람들은 로그 U가 고정 된 컴퓨터에서 상수라고 주장 할 것입니다. 32 비트 컴퓨터에서 모든 정수는 32 비트입니다 (단, 임의 정밀도 정수 라이브러리를 사용하는 경우는 제외). 64 비트 시스템에서는 모든 정수가 64 비트입니다. 첫 번째 경우에는 로그 U = 32이고 두 번째 로그에서는 U = 64입니다. 고정 시스템의 경우 radic sort 항상은 런타임이 O (n)이므로 선형 시간이 걸릴 수 있습니다. 그러나 상수는 시스템마다 다릅니다. 좀 더 이론적으로 생각하고 더 정확하게하고 싶다면 기수 정렬은 로그 U = O (1) 인 한 선형 시간으로 실행한다고 말할 수 있습니다. 그런 식으로 O (n log U) = O (n)입니다. 즉, 숫자의 비트 수에 대한 상한선이 상수이면 기수 정렬이 선형 시간으로 실행된다는 것을 의미합니다.
버킷 정렬 알고리즘은 최하위 자리보다 상위 자리를 사용하여 소자를 분배하는 것을 제외 정렬 기수 유사하다. 이는 분석이 이전과 거의 동일하다는 것을 의미합니다. 로그 U = O (1) 인 경우 알고리즘은 선형 시간으로 실행됩니다.
희망이 있습니다.
기수, IIRC는 항상 선형이지만 상수는 가장 큰 정수의 비트 수입니다. 따라서 32 비트 기수 정렬은 데이터에 대해 32 개의 선형 패스로 실행됩니다. N <2^32의 경우, mergesort와 같은 N 개의 N 개의 정렬이 더 빠릅니다. –
"선형 시간"이라고 말하면 어떤 매개 변수가 선형이 되려고합니까? 요소의 수는? 가장 큰 값의 비트 수는 얼마입니까? 총 비트 수는 얼마입니까? – templatetypedef
@templatetypedef 알고리즘의 실행 시간에 대해 이야기하고 있습니다. 재판관은 그렇습니다, 그들은 모두 선형 시간입니다, 그러나 최적의 경우가 언제인지, 실행 시간을 현명하게 이해하고 싶습니다. – ZAX