범위가 주어지면 배열의 숫자 빈도를 계산해야합니다. 주어진 솔루션이 효율적입니까?

Question

#include<iostream.h> 

int main() 
{ 
    int a[10]={1,2,3,5,2,3,1,5,3,1}; 
    int i; 
    int c[10]={0}; 

    for(i = 0 ; i < 10 ; i++) 
     c[a[i]]++; 

    for(i=0;i<10;i++) 
     cout<<i<<": "<<c[i]<<endl; 

    return 0; 
} 

알고리즘의 실행 시간은 O (n)이지만 O (n)의 추가 공간을 차지합니다. 더 잘할 수 있을까요?

감사합니다.

Answer 1

아니요. 그게 당신이 할 수있는 최선의 방법입니다.

Answer 2

O (n^2) 시간이지만 O (1) 공간 (두 개의 루프 사용, 아래 코드 참조)을 사용하는 알고리즘을 만들 수 있지만 시간 복잡도를 향상시킬 수는 없습니다. O (n) 이하.

for(i=0;i<10;i++) { 
    count = 0; 
    for(j=0;j<10;j++) 
    if (c[j] == i) count++; 
    cout<<i<<": "<<count<<endl; 
} 

O (1)의 공간에 대한 다른 possiblity가

시간 복잡도 O 있어야에서 적절한 배열의 정렬 후, 일단이 통과 될 것이다 (N 로그 n)에서 적절한 병합 정렬을 사용.

Answer 3

"효율적인"이란 무엇입니까? 실적 요구 사항 및 성과 측정 결과를 보여주십시오. 그런 다음 효율적인지 알려줄 수 있습니다. 그때까지 이것은 많은 잘못된 대답과 정답이없는 열린 질문입니다. 답변은 지금까지 올바른 단어 '능률적 인'은 '가능한 빨리 실행'을 의미합니다.

RAM이 적은 고속 컴퓨터를 가지고있을 수도 있습니다.

항상 코드 조각을 빠르게 만들거나 디스크 공간을 줄이거 나 사용량을 줄이거 나 메모리를 덜 사용할 수 있습니다. 충분히 효율적이지 않은 경우, 필자가 손으로 만든 공예품 조립품을보다 빠르게 볼 수 있습니다. 보통 그것은 시간과 노력의 낭비입니다. 프로파일되지 않은 최적화 코드는 바보 게임입니다.

Answer 4

모든 숫자가 1 ~ n 범위에 있으면 O (n) 시간 복잡도와 O (1) 공간 복잡도로 수행 할 수 있습니다.

A [X] = Y 인 인덱스 A와 A가있는 경우 인덱스 Y에있는 값에 N을 더합니다. A [Y]는 A [Y] = original + N이됩니다. 계속해서, 값은 k> = 0. 형태의 (original + KN) 형태가 될 것입니다. 원래의 원소를 검색하기 위해 (x + kn) % n = x부터 (N + 원 + KN)/N.