프로그래머스 / 콜라츠 추측 (Big-O표기법)

문제요약

// 콜라츠 추측 (아래 작업을 하면 모든 수를 1로 만들 수 있다는 추측)
// 1. 입력된 수가 짝수면 2로 나눕니다.
// 2. 입력된 수가 홀수면 3을 곱하고 1을 더합니다.
// 3. 이 작업을 1이 될 때까지 반복합니다.
// 위 작업을 몇 번해야 하는지 반환하라.
// 500번을 반복해도 1이 되지 않는다면 -1을 반환하라.

입출력 예시

// 6 -> 8
// 16 -> 4
// 626331 -> -1

수도코드

// 재귀의 기초 num이 1이 되거나, answer이 500이상이 되면 리턴한다.
// 콜라츠 추측의 조건들을 구현한다.

시간복잡도 O(1)

문제상황

처음에는 O(n)이라고 생각했다.
왜냐하면 O(500)이라서 500=1 이라는 게 와닿지 않았기 때문이다.
하지만 나는 빅오표기법은 상수를 버리는 특성을 가지고 있다는 걸 알고있었다.
이것저것 검색도 해보고, 혼자 생각도 해봤지만 O(1)인지 O(n)인지 헷갈렸다.
그래서 오픈채팅방에 물어봐서 O(1)이라는 것을 확신했다.

결론

아무리 반복해도 500회까지만 작동하니까. O(500) 이다. O(500) = O(1)
하지만 내가 구현한 코드는 아무리 데이터가 커져도 500번만 작동한다.
즉 데이터가 커질수록 연산횟수가 증가하는 O(n)이라고 할 수 없다.

코드

function solution(num) {
  let answer = 0;
  const collatz = function(num) {
    if (num === 1) {
      return answer;
    } else if (answer >= 500) {
      return -1;
    }
    answer ++;
    if (num % 2 === 0) {
      num = num / 2;
      return collatz(num)
    } else {
      num = num * 3 + 1;
      return collatz(num)
    }
  }
  return collatz(num)
}