해싱을 사용하여 배열을 정렬하면 성능상으로 어떤 단점이 있습니까?

Question

해시를 사용하여 배열 int a[];을 정렬하는 간단한 함수를 작성했습니다. 그 때문에 새로운 배열 hash1[]에있는 모든 요소에 대한 빈도를 저장 한 다음 선형 시간으로 원래 배열에 다시 넣습니다.

#include<bits/stdc++.h> 
using namespace std; 
int hash1[10000]; 
void sah(int a[],int n) 
{ 
    int maxo=-1; 
    for(int i=0;i<n;i++) 
    { 
     hash1[a[i]]++; 
     if(maxo<a[i]){maxo=a[i];} 
    } 
    int i=0,freq=0,idx=0; 
    while(i<maxo+1) 
    { 
     freq=hash1[i]; 
     if(freq>0) 
     { 
      while(freq>0) 
      { 
       a[idx++]=i;freq--; 
      } 
     } 
     i++; 
    } 
} 
int main() 
{ 
    int a[]={6,8,9,22,33,59,12,5,99,12,57,7}; 
    int n=sizeof(a)/sizeof(a[0]); 
    sah(a,n); 
    for(int i=0;i<n;i++) 
    { 
     printf("%d ",a[i]); 
    } 
} 

이 알고리즘은 O (max_element)에서 실행됩니다. 성능 (시간과 공간)만을 고려할 때 내가 직면 한 단점은 무엇입니까? 당신이 고려할 수 있습니다

Answer 1

구현 한 알고리즘은 counting sort입니다. n은 엘리먼트의 총 수이고, U는 어레이 (숫자는 0 내지 U 이동 가정)의 최대 값이며, 그 공간 사용 Θ (U) 여기서 그 런타임은 O (N + U)이다. 특정 구현에서는 U = 10,000이라고 가정합니다. 당신은 자신의 값에 따라 요소를 주위에 확산 (A 유통로이 정말 해시 아니다 "해시"(요소의 일부 기능을 계산하고 양동이에 넣어 해당 사용)로 접근 방법을 설명한 있지만).

U가 고정 된 상수 인 경우 런타임은 O (n)이고 공간 사용량은 O (1)이지만 장기 성장률에 대한 big-O 회담과 U가 크면 런타임이 상당히 높아질 수 있습니다. 제한된 범위의 값으로 매우 큰 배열을 정렬하는 경우 이는 매우 유용합니다. 그러나 값의 범위가 클 경우 특히 좋은 방법은 아닙니다. 흥미롭게도 기수 정렬은 U = 10 (숫자의 밑이 10 자리 인 경우) 또는 U = 2 (이진의 경우) 및 O (n의 런타임이있는 경우)를 사용하여 반복 계산하는 알고리즘으로 생각할 수 있습니다 여러 가지 방법으로 U.

당신이 코드를 정리할 수의 큰 값을 강하게 바람직하다 로그 U). 예를 들어, 당신은 if 문 단일 while 루프에 함께 결합 될 수있는 동일한 조건을 가진 while 루프를 가지고있다. 또한 모든 값이 0에서 9,999까지의 범위에 있는지 확인하기 위해 일부 어설 션 체크를 넣을 수도 있습니다. 그렇지 않으면 경계 오류가 발생하기 때문입니다. 또한 전역 배열을 로컬 변수 (스택 사용량을 보았지만) 또는 static (전역 네임 스페이스 오염을 방지하기 위해) 중 하나로 만들 수도 있습니다. 사용자가 최대 크기를 지정하는 매개 변수를 전달하거나 직접 계산할 수도 있습니다.

Answer 2

문제 :

• 입력 검증. 사용자가 -10 또는 매우 큰 값을 입력하면 어떻게 될까요? 최대의 요소가 큰 경우 L1 캐시가 소진 될 때
• , 당신은 어떤 점에서 성능 저하를 얻을 것이다. hash1 - 배열은 a - 배열과 메모리 대역폭을두고 경쟁합니다. 과거에 기수 정렬을 구현했을 때 반복 당 8 비트가 가장 빠름을 발견했습니다.
• 시간 복잡도 실제로 O (max_element number_of_elements +)이다. 예 : 2 백만 개의 1 또는 0을 정렬하면 어떨까요? 2 개 또는 0을 정렬하는 것만 큼 빠르지 않습니다.