재귀 함수의 복잡성 결정 (Big O 표기법)

재귀 함수의 복잡성 결정 (Big O 표기법)

---

나는 내일 Computer Science Midterm을 가지고 있으며 이러한 재귀 함수의 복잡성을 결정하는 데 도움이 필요합니다. 간단한 사례를 해결하는 방법을 알고 있지만 여전히 어려운 사례를 해결하는 방법을 배우려고 노력하고 있습니다. 이것들은 내가 알아낼 수없는 몇 가지 예제 문제 일뿐입니다. 도움을 주시면 제 연구에 큰 도움이 될 것입니다. 감사합니다!

int recursiveFun1(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun1(n-1);
}

int recursiveFun2(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun2(n-5);
}

int recursiveFun3(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun3(n/5);
}

void recursiveFun4(int n, int m, int o)
{
    if (n <= 0)
    {
        printf("%d, %d\n",m, o);
    }
    else
    {
        recursiveFun4(n-1, m+1, o);
        recursiveFun4(n-1, m, o+1);
    }
}

int recursiveFun5(int n)
{
    for (i = 0; i < n; i += 2) {
        // do something
    }

    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun5(n-5);
}

---

각 함수에 대한 Big O 표기법의 시간 복잡도는 숫자 순서입니다.

1. 첫 번째 함수는 기본 사례에 도달하기 전에 n 번의 재귀 적으로 호출되므로 선형O(n) 이라고도 합니다.
2. 두 번째 함수는 매번 n-5라고 불리우므로 함수를 호출하기 전에 n에서 5를 빼지 만 n-5도입니다 O(n). (실제로 n / 5 번의 순서라고하며 O (n / 5) = O (n)).
3. 이 함수는 log (n) base 5이며, 함수를 호출하기 전에 5로 나눌 때마다 O(log(n))( 대수 5) ( 대수 라고도 함)이며 Big O 표기법 및 복잡도 분석은 밑수 2를 사용합니다.
4. 네 번째에서는 n 또는 recurs되지 않는 한 각 함수 호출이 자신을 두 번 호출하기 때문에 O(2^n), 즉 지수 입니다.

5. 마지막 함수의 경우 for 루프는 2 씩 증가하기 때문에 n / 2가 걸리고 재귀는 n-5가되고 for 루프는 재귀 적으로 호출되므로 시간 복잡도는 (n-5) * (n / 2) = (2n-10) * n = 2n ^ 2- 10n은 점근 적 행동과 최악의 시나리오 고려 사항 또는 big O가 노력하는 상한으로 인해 가장 큰 항에만 관심이 O(n^2)있습니다.

   중간에 행운을 빕니다;)

---

여기서 사건의 경우 n <= 0, T(n) = O(1). 따라서 시간 복잡도는시기에 따라 달라집니다 n >= 0.

n >= 0아래 부분 에서 사례 를 고려할 것 입니다.

1.

T(n) = a + T(n - 1)

여기서 a는 상수입니다.

유도하여 :

T(n) = n * a + T(0) = n * a + b = O(n)

여기서 a, b는 상수입니다.

2.

T(n) = a + T(n - 5)

a는 상수입니다

유도하여 :

T(n) = ceil(n / 5) * a + T(k) = ceil(n / 5) * a + b = O(n)

여기서 a, b는 상수이고 k <= 0

삼.

T(n) = a + T(n / 5)

a는 상수입니다

유도하여 :

T(n) = a * log5(n) + T(0) = a * log5(n) + b = O(log n)

여기서 a, b는 일정하다

4.

T(n) = a + 2 * T(n - 1)

a는 상수입니다

유도하여 :

T(n) = a + 2a + 4a + ... + 2^n * a + T(0) * 2 ^ n 
     = a * 2^(n+1) - a + b * 2 ^ n
     = (2 * a + b) * 2 ^ n - a
     = O(2 ^ n)

여기서 a, b는 상수입니다.

5.

T(n) = n / 2 + T(n - 5)

우리는 T(5k) >= T(5k - d)d = 0, 1, 2, 3, 4 인 것을 유도함으로써 증명할 수 있습니다

다음과 같이 쓴다 n = 5m - b(m, b는 정수이고 b = 0, 1, 2, 3, 4) m = (n + b) / 5.

T(n) = T(5m - b) <= T(5m)

(사실, 새로운 기능, 여기에 더 엄격 할 수 T'(n)있도록 정의되어야한다 T'(5r - q) = T(5r)어디 q = 0, 1, 2, 3, 4우리는 알고있다. T(n) <= T'(n)위의 입증한다. 우리가 알고있는 경우 T'(n)에 O(f), 그래서 B를 상수가 존재하는 의미, T'(n) <= a * f(n) + b우리가 있음을 유도 할 수있다 T(n) <= a * f(n) + b따라서 T(n)이다 에서 O(f).이 단계는 정말 필요하지 않습니다,하지만 당신은 나머지 처리하지 않을 때 생각하는 것이 더 쉽습니다.)

확장 T(5m):

T(5m) = 5m / 2 + T(5m - 5) 
      = (5m / 2 + 5 / 2) * m / 2 + T(0) 
      = O(m ^ 2) = O(n ^ 2)

따라서 T(n)입니다 O(n ^ 2).

---

재귀 알고리즘의 복잡성을 근사화하는 가장 좋은 방법 중 하나는 재귀 트리를 그리는 것입니다. 재귀 트리가 완성되면 :

Complexity = length of tree from root node to leaf node * number of leaf nodes

1. 첫 번째 함수는 길이 n와 리프 노드 수를 가지 1므로 복잡도는n*1 = n

2. 두 번째 함수는 n/5다시 리프 노드 의 길이 와 수를 가지 1므로 복잡성이 커집니다 n/5 * 1 = n/5. 대략적으로n

3. 세 번째 함수의 경우 n모든 재귀 호출마다 5로 나뉘어 지기 때문에 재귀 트리의 길이는 log(n)(base 5)1이고 리프 노드 수는 다시 1이므로 복잡도는log(n)(base 5) * 1 = log(n)(base 5)

4. 네 번째 함수의 경우 모든 노드에 두 개의 자식 노드가 있기 때문에 리프 노드의 수는 같고 (2^n)재귀 트리의 길이는 n복잡 할 것 (2^n) * n입니다. 그러나 n앞에서는 중요하지 않기 때문에 (2^n)무시할 수 있고 복잡성 만 말할 수 있습니다 (2^n).

5. 다섯 번째 함수에는 복잡성을 나타내는 두 가지 요소가 있습니다. 재귀 함수의 기능으로 인해 발생하는 복잡성과 for각 함수에서 루프로 발생하는 복잡도 위의 계산을 수행하면 재귀 함수의 기능 ~ n으로 인한 복잡성과 for 루프로 인한 복잡성이 발생합니다 n. 총 복잡성은 다음과 같습니다 n*n.

참고 : 이것은 복잡성을 계산하는 빠르고 더러운 방법입니다 (공식 없음). 이에 대한 의견을 듣고 싶습니다. 감사.

참고 URL : https://stackoverflow.com/questions/13467674/determining-complexity-for-recursive-functions-big-o-notation