mergesort의 카운팅 비교

파이썬으로 mergesort를 만들었고 제대로 작동하고 있습니다.이 병합 정렬이 실행 중일 때 비교를해야합니다. 재귀 함수이기 때문에 전역 변수 'merge_compare_count'를 선언합니다. 그리고 목록 A의 원소에 난수를 사용합니다.mergesort의 카운팅 비교

하지만이 코드를 실행할 때마다 항상 동일한 merge_compare_count가 있습니다. 나는 5000 개 무작위로 다른 요소를 가지고 있지만 항상 123616.

어떤 도움을 주셔서 감사합니다

과 같은 반환 merge_compare_count 예를 들어

, ... 이유를 알고하지 않습니다!

출처

2016-11-06 Dkyo Jeong

왜 그런가요? –

listA는 무작위로 다른 수의 요소를 가지고 있기 때문에 항상 같은 결과가 이상합니다 ... 나는 생각합니다 .... –

전혀 이상하지 않습니다. 또한 올바르게 들여 쓰기하고 "500"을 "5000"으로 수정하십시오. –

그건 문제가되지 않습니다. 작성된 방식대로 코드에는 값이 아니라 크기에 따라 결정 단계의 결정적 개수가 있습니다. 다음과 같이 계산할 수도 있습니다.

>>> def f(n): 
     return 0 if n < 2 else f(n/2) + f(n-n/2) + 2*n 

>>> f(5000) 
123616

출처

2016-11-06 15:55:57

또는 * just * over 2 xnx log2 (n) 이는 O (NlogN) 알고리즘에 대해 전적으로 예상됩니다. –

감사합니다! 나는 그것을 얻었다!! –

@MartijnPieters 예, 특히 Θ (n log n)의 경우입니다. 놀랍지 않게 실제로는 거의 정확히 2n⋅log2 (n)입니다. 2의 제곱을 위해, 그것은 정확하게 그 것이다. –

mergesort의 카운팅 비교

답변

관련 문제