quicksort의 특정 버전을 어떻게 분석합니까?

나는이 의사를 가지고 있고이 알고리즘의 분석 시간 복잡하고 싶지만quicksort의 특정 버전을 어떻게 분석합니까?

Proc Sort(A,l,r) 
if(r-l+1<4) 
    then Quicksort(A,l,r) 
    else 
    Sort(A,l,r-3) 
    Sort(A,l+3,r)

그래서 나는 배열의 요소가 4보다 작 으면 우리가 퀵 통해 통과 알고에 대해 아무 생각이 그렇지 않으면 우리는 배열의 크기를 3 줄인 다음 왼쪽과 오른쪽 부분을 전달합니다. 그래서 우리는 이것을 수행하여 크기의 배열을 정확하게 얻습니다. < 4 문제는 재발 할 수없고 확실하지 않습니다. 이 알고리즘이 최악의 상황에서 더 잘 작동하는 경우 분석

도움 주셔서 감사합니다.

출처

2017-01-25 amir

인터넷에 관한 많은 정보가 있습니다. 그리고 yor text book. 그냥 검색해. –

당신은'Sort'라는 함수를 가지고 있고, 그 안에서'sort'와'Quicksort'를 호출합니다. 무엇 이니? 그리고 이것은 기본 케이스를 가지고있는 것처럼 보이지 않으므로 그것이 영원히 달릴 것처럼 보입니다. – Carcigenicate

죄송합니다 이것이 내 잘못이었습니다.이 함수는 정확합니다. – amir

음,이 정렬 기능 실제로 작동 여부, 실행 시간을 파악하는 방법은 여기에 아주 쉽게

당신은 배열 크기의 함수로 실행 시간에 대한 수학적 표현을 적어 :

T (N) = ???

글쎄, N < = 4이면 Quicksort를 부릅니다. 이제는 함수 정의를 사용할 수 없지만 그 크기에 관계없이 최대 크기 4의 입력으로 호출되기 때문에 실행 시간을 상수로 처리하고 C로만 호출 할 수 있습니다.

그리고 만약 N> = 4라면, 우리는 Sort를 다시 호출합니다. 배열은 3보다 작습니다. 그래서

: N> = 4

T (N)은 2 * T이다 (N-3).

이제 런타임 분석에 필요한 모든 정보를 제공해야합니다. 네가 붙어있을 때 여기에서 해보고 우리에게 돌아가는게 어때?

출처

2017-01-25 18:13:46 Lagerbaer

고맙습니다.이 재귀를 해결하려고하면 유도를 사용하여 T (n) = O (2^(N/3) -1)? – amir

오른쪽에 대한 소리! – Lagerbaer

quicksort의 특정 버전을 어떻게 분석합니까?

답변

관련 문제