1
배열의 가장 작은 n/(log n) 요소를 O(n)에 정렬하는 방법은 무엇입니까?배열의 가장 작은 n/logn 요소를 정렬하십시오.
내가 가장 작은 k 요소를 정렬하는 방법을 알고 있지만 O(n+k*log k)이지만 내 질문에 이것을 사용하는 방법?
A
답변
4
k = n/(log n)이면 알고있는 알고리즘을 사용하면 O (n + (n/(log n)) * log (n// (log n), log n> log (n/(log n))이므로 O (n)이됩니다.
1
나는 기존 솔루션이 이미 트럭을 수행 생각 : 당신이
k = n/(log n)
를 대체 할 경우
total = O(n + (n/log n) * log (n/log n))
이 log (a/b) = log a - log b을 사용하여 얻을 :
total = O(n + (n/log n) * (log n) - (n/log n) *log log n)
total = O(n + n - (n/log n) *log log n)
우리는 부정적인 용어를 멀리 던질 수 : O(f) 인 것보다 f < g 인 경우
total = O(n)
O(g)
total = O(2 * n)
수, 큰-O는 우리가 일정한 요인을 무시할 수 있습니다
관련 문제
- 1. 가장 큰 것에서 가장 작은 것까지 무작위 배열의 목록을 정렬하십시오.
- 2. 배열의 제품을 패키지로 정렬하십시오.
- 3. 배열의 가장 작은 숫자 python
- 4. 배열의 차이가 가장 작은 두 요소를 찾는 방법은 무엇입니까?
- 5. ListMap : 가장 작은 값을 가진 m 개의 가장 작은 요소를 제거하십시오.
- 6. 배열에서 가장 작은 요소를 찾습니다.
- 7. 배열의 가장 작은 요소의 인덱스를 반환하십시오.
- 8. 행과 열의 요소를 정렬하십시오.
- 9. TableRow의 구성 요소를 정렬하십시오.
- 10. 두 요소를 xQuery로 정렬하십시오.
- 11. 배열에서 가장 작은 요소를 찾는 재귀 알고리즘
- 12. 배열에서 가장 작은 요소를 찾기위한 루프
- 13. 배열의 가장 큰 값과 가장 작은 값을 표시하는 방법
- 14. 배열의 중복 요소를 반환하는 가장 좋은 방법은
- 15. Yesod에서 양식 요소를 가로로 정렬하십시오.
- 16. 어떤 것이 더 빠릅니까? 작은 배열의 요소를 정렬하거나 배가 시키시겠습니까?
- 17. OpenMP가 가장 작은 가장 작은 타임 슬라이스
- 18. PHP : 배열을 다른 배열의 문자 순서로 정렬하십시오.
- 19. R - 배열의 요소를 특성화합니다.
- 20. C 배열의 많은 요소를 제거하는 가장 빠른 방법
- 21. 배열의 세 번째로 작은 요소
- 22. 배열의 각 문자열에 대한 가장 작은 고유의 문자열을 찾기
- 23. 배열의 요소와 요소를 반복합니다.
- 24. 루프 물마루 jQuery 요소를 그림과 같이 정렬하십시오.
- 25. 편집기 템플릿 두 구성 요소를 정렬하십시오.
- 26. 배열의 배열의 가장 빈번한 배열
- 27. 큰 배열 안에있는 다른 배열의 값에 따라 큰 배열을 정렬하십시오.
- 28. 목록에서 가장 작은 k 요소를 찾는 더 효율적인 솔루션
- 29. 추력/cudpp 알고리즘 k 번째 가장 작은 요소를 찾으십시오
- 30. 어떻게 PHP 배열에서 가장 작은 번호가 매겨진 요소를 얻을 수