All Articles

Recursive(재귀호출) 의 Big O 는 어떻게 될까? leetcode 1342. Number of Steps to Reduce a Number to Zero

문제: Number of Steps to Reduce a Number to Zero

문제는 너무 쉬웠다. 바로 풀었는데 (내가 알고리즘 천재인줄 앎)

leetcode 1342 calculate recursive big o number of steps to reduce a number to zero

Given a non-negative integer num, return the number of steps to reduce it to zero. If the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.

갑자기 Recursive 의 Big O 가 궁금하다는 생각이 들었다.(갑자기)

검색하다 보니 stack overflow 에 좋은 글을 찾았다.

Determining complexity for recursive functions (Big O notation) 라는 글을 찾게 되었다.

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

이건 base case ( n0n ≤ 0 ) 까지 도착하는데 n 번 recursive 된다.

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

base case 에 오는데 n5n-5 번 걸리지만 결국 같은 O(n)O(n) 이 된다.

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

이 함수는 log(n)log(n) 이 된다. 왜냐하면 매번 함수를 호출 하기 전에 divide by 5 가 되기 때문이다.

그런데 매번 5씩 나누는거랑 log 랑 무슨 상관이 있는거지..?

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

일단 수식이 이러하다고 함. (a, b 는 상수)

  1. n = 0 이면 1번 호출
  2. 1 ≤ n < 5 이면 2번 호출
  3. 5 ≤ n < 25 이면 3번 호출
  4. 25 ≤ n <125 이면 4번 호출

이러한 이유로 밑이 5인 log 가 완성된다.

최대 1+log5n1 + log_5n

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);
    }
}

이건 2n2^n 이거나 exponential 이라고 한다. 왜냐하면 함수가 recursive n을 각각 두번 호출하기 때문이다. 사실 이게 2n2^n 이 될 거라고 생각 못했다. 그리고 대부분의 recursive 가 다 이런 높은 OO 를 가지고 있는줄 알았어서 최대한 recursive 를 피하는 방향으로만 생각했다.

int recursiveFun5(int n) {
    for (i = 0; i < n; i += 2) {
        // do something
    }
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun5(n-5);
}

첫 번째 for 문 에서 n/2n/2 호출이 된다, for 문이 2 씩 증가 한다.

그리고 n-5 번 호출하는 recursive 가 있다.

따라서 수식은 (n/2)(n5)=(2n10)n=2n210n(n / 2) *(n -5) = (2n -10)* n = 2n^2 - 10n

O(n2)O(n^2) 가 된다.

recursive 라고 무조건 피하는 게 아니라 잘 따져볼 필요가 있다.

이제 문제를 보면

class Solution {
    public int numberOfSteps (int num) {
        int result = 0;
        while(num > 0) {
            if (num % 2 == 0) {
                num /= 2;
            } else {
              num -= 1;  
            }
            result ++;
        }
        return result;
    }
}

최초에 내가 푼 풀이다. 사실 DP 로도 접근을 해봤다. 왠지 DP로 하면 잘 맞아떨어질거 같다는 생각이 들었기 때문이다.

  • 9: 8의 결과 +1; (9, 8, 4, 2, 1)
  • 10: 10, 5, 4, 2, 1, 0
  • 11: 10의 결과 + 1; (11, 10, 5, 4, 2, 1, 0)
  • 12: 6의 결과 + 1;
  • 13: 12의 결과 + 1; (13, 12, 6, 3, 2, 1, 0)
  • 14: 7의 결과 + 1; (14, 7, 6, 3, 2, 1, 0)

그런데 DP 로 한다면 캐싱이 필수이기 때문에 공간을 두어서 오히려 속도가 엄청 느려진다

calculate recursive big o number of steps to reduce a number to zero

DP로 푼것 하나만 343ms 로 나온다

class Solution {
    public int numberOfSteps (int num) {
        if (num <= 1) return 1;
        if (num % 2 == 0) {
            return 1 + numberOfSteps(num/2);          
        } else {
            return 1 + numberOfSteps(num-1);
        }
    }
}

이 풀이는 recursive 로 푼 경우인데

worst case 가 n-1, n/2 가 번갈아 나오는 경우이다.

그렇다면 무조건 -1 이 되는 n 보다 빠르고, log2log_2 보다는 느리게 된다.

즉, Big O notation 로는 lognlog_n 이라 볼 수 있다.(while 을 사용한 경우도 맞찬가지)

그리고 Big O 를 검색하다 보니 big o cheat sheet 이런 멋진것도 발견했다.

big o cheat sheet

big o cheat sheet

알고리즘으로 고생하고 계신분들이 있다면, 많은 도움 되시길 :)