c - 측정 - 자바 스크립트 시간 복잡도

재귀 알고리즘의 시간 복잡도 (4)

재귀 알고리즘의 시간 복잡도는 어떻게 계산합니까?

int pow1(int x,int n) {
    if(n==0){
        return 1;
    }
    else{
        return x * pow1(x, n-1);
    }
}

int pow2(int x,int n) {
    if(n==0){
        return 1;
    }
    else if(n&1){
        int p = pow2(x, (n-1)/2)
        return x * p * p;
    }
    else {
        int p = pow2(x, n/2)
        return p * p;
    }
}

pow1로 시작해 보겠습니다. 왜냐하면 가장 간단한 것이기 때문입니다.

O (1)에서 단일 실행이 수행되는 기능이 있습니다. 조건 검사, 반환 및 곱셈은 일정한 시간입니다.

당신이 남긴 것은 재귀입니다. 함수가 자신을 호출하는 빈도를 분석하는 일만하면됩니다. pow1에서는 N 번 발생합니다. N * O (1) = O (N).

pow2에 대해서도 같은 원칙이 있습니다. 함수의 단일 실행은 O (1)에서 실행됩니다. 그러나 이번에는 매번 N을 반으로 줄여야합니다. 즉, log2 (N) 회 실행합니다 - 효과적으로 비트 당 한 번. log2 (N) * O (1) = O (log (N)).

재귀가 항상 반복으로 표현 될 수 있다는 사실을 이용하는 것이 도움이 될만한 것 (항상 간단하지는 않지만 가능하지만 pow1을 다음과 같이 표현할 수 있습니다.

result = 1;
while(n != 0)
{
  result = result*n;
  n = n - 1;
}

이제 반복 알고리즘을 대신 사용할 수 있습니다. 그런 식으로 분석하는 것이 더 쉬울 수도 있습니다.

그것은 약간 복잡 할 수 있습니다. 그러나 저는 평소에 Master 's theorem 을 사용하는 것이 좋다고 생각합니다.

재귀 함수 분석 (또는 평가)은 중요하지 않은 작업입니다. Don Knuths Concrete Mathematics 에서는 (제 의견으로는) 좋은 소개를 찾을 수 있습니다.

그러나 이제 다음 예제를 분석해 보겠습니다.

우리는 함수에 필요한 시간을 제공하는 함수를 정의합니다. t(n) 은 pow(x,n) 필요한 시간, 즉 n 의 함수를 나타냅니다.

그러면 우리는 pow(x,0) 호출하면 ( n==0 )을 확인한 다음 1을 반환해야하기 때문에 t(0)=c 라고 결론 지을 수 있습니다. 상수 c ).

이제 우리는 다른 경우를 고려합니다 : n>0 . 여기서 우리는 t(n) = d + t(n-1) 을 얻는다. 왜냐하면 우리는 다시 n==1 을 체크하고 pow(x, n-1 , 따라서 t(n-1) )를 계산하고 결과에 x 곱하기 때문입니다. ), pow 의 재귀 계산은 t(n-1) .

이제 우리는 용어 t(n) "확장"할 수 있습니다.

t(n) =
d + t(n-1) = 
d + (d + t(n-2)) = 
d + d + t(n-2) = 
d + d + d + t(n-3) =
... =
d + d + d + ... + t(1) =
d + d + d + ... + c

그렇다면 t(1) 도달 할 때까지 얼마나 걸리나요? 우리는 t(n) 에서 시작하고 각 단계에서 1을 빼기 때문에 t(n-(n-1)) = t(1) 에 도달하려면 n-1 단계가 필요합니다. 그것은 다른 한편으로, 상수 d 의 n-1 배를 얻음을 의미하며, t(1) 은 c 로 평가됩니다.

그래서 우리는 얻는다.

t(n) =
...
d + d + d + ... + c =
(n-1) * d + c

그래서 우리는 O (n)의 원소 인 t(n)=(n-1) * d + c 를 얻습니다.

pow2 는 석사 정리를 사용하여 수행 할 수 있습니다. 알고리즘의 시간 함수는 단조롭게 증가한다고 가정 할 수 있기 때문에. 이제 pow2(x,n) 의 계산에 필요한 시간 t(n) 가 있습니다 :

t(0) = c (since constant time needed for computation of pow(x,0))

n>0 대해 우리는 얻는다.

        / t((n-1)/2) + d if n is odd  (d is constant cost)
t(n) = <
        \ t(n/2) + d     if n is even (d is constant cost)

위의 내용은 다음과 같이 "단순화"할 수 있습니다.

t(n) = floor(t(n/2)) + d <= t(n/2) + d (since t is monotonically increasing)

따라서 t(n) = O(log n) 대한 masters theorem을 사용하여 해결할 수있는 t(n) <= t(n/2) + d 를 얻을 수 있습니다. "이원 검색").

재귀를 무시한 두 함수의 복잡도는 O (1)입니다.

첫 번째 알고리즘의 경우 pow1 (x, n) 복잡도는 O (n)입니다. 재귀 심도가 n과 선형으로 관련되기 때문입니다.

두 번째 복잡성은 O (log n)입니다. 여기서 우리는 log2 (n) 번 정도 재연합니다. 2를 버리면 로그 n이 나온다.