QuickSort의 최악의 실행 시간 증명.

Question

나는 효율적인 방법으로 다음의 재귀 함수에 대한 점근 분석을 시도하고있다. 나는 힘이 홀수이고 힘이 짝수 일 때 다른 방정식을 가짐으로써 재발 방정식을 결정하는 데 어려움을 겪고있다. 나는이 상황을 어떻게 처리해야하는지 확신 할 수 없다. 나는 실행 시간이 쎄타 (logn)라는 것을 이해하므로이 결과를 진행하는 방법에 대한 조언을 주시면 감사하겠습니다.

Recursive-Power(x, n): 
if n == 1 
    return x 
if n is even 
    y = Recursive-Power(x, n/2) 
    return y*y 
else 
    y = Recursive-Power(x, (n-1)/2) 
    return y*y*x 

Answer 1

은 어떤 경우, 다음과 같은 조건을 원하는 분야 floor(n) 가장 큰 정수 크지 n보다

T(n) = T(floor(n/2)) + Θ(1) 

.

T(n) = T(n/2) + Θ(1) 

당신은 제대로 바인딩 점근을 짐작 :로 floor 이후

결과에 영향이없는, 방정식은 비공식적으로 기록됩니다. 그 결과는 대체 방법 또는 마스터 정리를 사용하여 증명할 수 있습니다. 그것은 당신을위한 운동으로 남아 있습니다.