알고리즘 복잡도 계산실습

gistfile1.md

시작하기에 앞서

• 소스코드를 업데이트 했습니다. 아래의 링크에서 확인가능합니다.

• https://github.com/dobestan/NHN_NEXT_2014_01_C_Programming/blob/master/20140404/homework/hw03_4.c

• 단순히 연산 순서를 알아보기 위한 소스로 중복체크는 되지 않습니다.

• 시간 복잡도로 계산해보도록 하자.

• O(N)으로 표시한다.

Iterative Algorithm

void print_options(int money) {
  for ( int i = 1 ; i <= money / bread ; i++ ) {
    for ( int j = 1 ; j <= (money - i * bread) / snack ; j++) {
      for ( int k = 1 ; k <= (money - i * bread - j * snack) / drink ; k++ ) {
        if ( money == i*bread + j*snack + k*drink ) printf("BREAD(%d), SNACK(%d), DRINK(%d)\n", i , j, k );
      }
    }
  }
}

• money를 변수 n이라고 봐도 무방하다.
• bread, snack, drink 같은 경우에는 어차피 상수이므로 무시하고 생각하도록 한다.
• 즉, ( money - 상수 ) 횟수만큼 연산하는 알고리즘의 복잡도는 O(n)으로 볼 수 있다. for ( int i = 0 ; i < money - CONSTANT ; i++ ) 의 복잡도는 O(n)이라고 생각할 수 있다.
• 따라서 이 문제의 경우 iterative한 방식으로 풀 경우, 시간복잡도는 O(n^3)이다.
• 직관적으로 생각해보면 과자 개수가 k개일 때, 알고리즘의 복잡도는 O(n^k)이다.

Recursive Algorithm

void print_options_recursive(int money, int bread, int snack, int drink) {
  // Usage : print_options_recursive(get_current_money()-(BREAD + SNACK + DRINK), 1, 1, 1);

  if ( money < 0 ) return;
  if ( money == 0 ) printf("BREAD(%d), SNACK(%d), DRINK(%d)\n", bread , snack, drink );

  print_options_recursive(money - BREAD, bread+1, snack, drink);
  print_options_recursive(money - SNACK, bread, snack+1, drink);
  print_options_recursive(money - DRINK, bread, snack, drink+1);
}

• 간단하게 생각해보자. 상수는 모두 무시하고 호출 횟수에 대해서만 신경쓰도록 한다.
• 메모리 호출 순서도를 그려보자.
• 횟수를 잘 생각해보면 1회 실행 -> 3회 실행 -> 9회 실행 ... 이렇게 3^n 만큼 익스포넨셜하게 증가한다.
• 시간 복잡도는 O(3^n)임을 알 수 있고, 일반화하여 생각하면 과자 개수가 k개 일 때, O(k^n)임을 알 수 있다.

결론

• iterative method : O(n^k)
• recursive method : O(k^n)

물론 상수값에 따라서 차이가 있을 수 있지만, 일반적으로는 이 문제의 경우에는 Iterative한 방식이 Recursive한 방식에 비해서 시간 복잡도의 관점에서는 더 우수한 방식이다. 물론 공간 복잡도(메모리)는 시간 복잡도와 반비례하는 경향성이 있으므로 공간 복잡도의 관점에서는 Recursive한 방식이 더 우수하다고 생각할 수 있다. 일반적으로는 ( 우리는 시간 복잡도로 생각한다고 하면 ) Iterative한 방식이 우수한 방식이나, n(변수 ; 가지고 있는 돈)의 범위나 k(상수 ; 과자의 가격)값에 따라 적절한 알고리즘을 사용해야한다고 판단된다.