1
I 알고리즘 분석에서 시험 exercies 통해 예정이 그들 중 하나 : 입력으로 N 개의 요소의 목록을 얻어특정 알고리즘 정렬 N 소자
현재 알고리즘 (즉, 은 비교할 수 있음) O (nlog m) 시간에 정렬합니다. 여기서 m은 입력 목록에있는 고유 한 값의 수입니다 (예 : ).
나는 일반적인 정렬 알고리즘에 대해 읽었으며 정말 해결책을 찾지 못했습니다. 당신의 도움이
A
답변
8
당신은 n 요소 증강 균형 이진 검색 트리를 구축 할 수 있습니다에 대한
감사합니다. 각 노드에 저장된 증강 정보는 빈도수입니다. 트리에 n 삽입을 사용하여이 구조를 구축하면 노드 수는 m이므로 O(n lg m)이됩니다. 그런 다음이 트리를 순차적으로 탐색합니다. 왼쪽 하위 트리를 방문하여 루트 f 번에 저장된 요소를 인쇄하고 f은 빈도입니다 (이 정보는 증가 된 정보 임). 마지막으로 오른쪽 하위 트리를 방문합니다. 이 통과에는 시간이 걸릴 것입니다 O(n + m). 따라서이 간단한 절차의 실행 시간은 O(n lg m + n + m) = O(n lg m)이고 이됩니다.
관련 문제
- 1. Big-Theta (n) 선형 정렬 알고리즘?
- 2. , 소자
- 3. C++ 정렬 알고리즘 기간
- 4. 특정 상황에 대한 가장 빠른 정렬 알고리즘
- 5. 순차 정렬 알고리즘
- 6. 비교 정렬 알고리즘 복잡성
- 7. 정렬 알고리즘
- 8. 정렬 알고리즘
- 9. n 차원 매칭 알고리즘
- 10. 2^n 복잡도 알고리즘
- 11. 효율적인 문자열 정렬 알고리즘
- 12. 바이너리 삽입 정렬 알고리즘
- 13. Kruskal의 알고리즘 (정렬)
- 14. 거리의 n * n 행렬에 대한 질문 알고리즘
- 15. O (2^n * n) 배낭 알고리즘
- 16. 충돌 탐지를위한 O (n^log n) 알고리즘
- 17. : 의사 소자
- 18. 일부 노드 정렬 알고리즘
- 19. 정렬 알고리즘 : 출력
- 20. 초보자를위한 알고리즘 정렬
- 21. n 차원 보간법 C++ 알고리즘
- 22. 정렬 알고리즘 팩토리에는 어떤 매개 변수가 있습니까?
- 23. O (fib n) 복잡도 알고리즘?
- 24. 알고리즘 화면에 이미지 정렬
- 25. Java 정렬 알고리즘
- 26. 도움말이 정렬 알고리즘 결정
- 27. 가역 정렬 알고리즘?
- 28. 병합 정렬 알고리즘 조언
- 29. 대기열에서 정렬 알고리즘 사용?
- 30. 해시 기반 정렬 알고리즘 만들기
'O (n + m)'에서 이것을 해결하는 것도 가능합니다. 계산 방식을 살펴보십시오. –
아마도 'O (n log m)'는 요소가 단지 비교 가능할 때 (인덱스로는 사용할 수없는 경우) 일어나는 일일 수 있습니다. 따라서 나뭇잎에 카운터가있는 m 요소의 균형있는 BST를 작성한 다음 계산을 수행해야합니다 m 카운터의 간단한 배열 대신 정렬하십시오. – harold
@harold 자기가 균형을 이진 검색 트리를 사용하여 [이진 트리 정렬] (http://en.wikipedia.org/wiki/Binary_tree_sort)를 참조하는 것 같아요,하지만 난 아직도 어떻게 O를 얻을 것이라고 볼 수 없어 n log m)? – HischT