크기 n의 입력에 대해 n의 값이 삽입 정렬 비트 병합 정렬을 수행합니까?

Question

알고리즘 소개 (Corman)에서 연습 1.2-2는 삽입 정렬 및 병합 정렬의 구현을 비교하는 것에 대한 다음 질문을 묻습니다. 크기 n의 입력의 경우 삽입 정렬은 8n^2 단계에서 실행되고 병합 정렬은 64n lg n 단계에서 실행됩니다. n 값은 삽입 정렬 병합 정렬을 수행합니까?

비록 대답에 관심이 있지만 가능한 단계적으로 대답을 찾는 방법에 관심이 있습니다 (가능한 모든 두 알고리즘을 비교할 수 있도록 프로세스를 반복 할 수 있도록).

언뜻보기에이 문제는 5 년 전에 취한 수업 인 비즈니스 미적분에서 휴식 지점을 찾는 것과 비슷하게 보였습니다. 그러나 어떤 도움을 주시면 감사하겠습니다.

내 태그가 잘못된 경우

P는/S는,이 질문은 잘못 분류 감사, 또는 다른 규칙으로, 최소로 응징을 제한하십시오 여기에 악용되고있다 이 질문을 게시 한 것은 이번이 처음입니다.

Answer 1

당신은 삽입 정렬의 비트 정렬

8n^2<=64nlogn 
n^2<=8nlogn 
n<=8logn 

n-8logn = 0 해결에 병합 당신이

n = 43.411 

그래서 n<=43에 삽입 정렬 병합 정렬보다 더 나은 작품에 도착하면 찾을 수 있기 때문에.