정의

는 임의의 함수 에 대하여 이 커질수록 의 값이 에 수렴하게 하는 함수를 말한다.

그리고 이 커질수록 의 값이 에 수렴하는 경우를 말한다.1

틸다 표기법의 특징은 다음과 같다.

  • 수식에 ~를 사용하여 수식을 읽는 사람에게 틸다 근사가 적용되었음을 알린다.
  • 수식에서 영향력이 적은 낮은 자리수의 항을 제거하여 간단하게 만든다.

틸다 근사 의 정규적인 수학적 정의는

이다.2

  • 틸다 근사는 점근 근사의 한 종류이다. [[big-O-notation]]{big O 근사}도 점근 근사에 해당한다.

틸다 근사의 예

틸다 근사를 쉽게 표현하자면 다음과 같다.

함수 틸다 근사 big O

예를 들어 은 [[big-O-notation]]으로는 이지만, 틸다 표현법에서는 이다.

3을 남겨두지 않으면 1 이 아니라 3이 되기 때문이다.

big O 표기법에 대한 틸다 표기법의 장점

Q. (위 질문에 이어서) 점근적인 성능에 있어서 그 상한은 중요하지 않나?

중요하다. 하지만 구문의 실행 빈도 관점에서의 정확한 값이 반영된 비용모델을 더 선호한다. 왜냐하면 그것이 알고리즘의 성능에 대해 더 많은 정보를 주고, 이 책에서 다루는 알고리즘들은 정확한 실행 빈도를 구해낼 수 있는 수준이기 때문이다. 예를 들어 "ThreeSum은 번의 배열 접근을 한다" 그리고 "ThreeSum에서 cnt++가 수행되는 최악 조건 횟수는 이다"라고 기술하면 다소 번거롭기는 하지만 "ThreeSum의 실행 시간은 이다"라고 하는 것보다 훨씬 더 풍부한 정보를 제공한다. 3

참고로 위의 인용에서 말하는 ThreeSum의 코드는 다음과 같다.

/**
 * 합계가 0이 되는 트리플을 카운팅하여 리턴한다.
 *
 * @param numbers 입력 숫자 배열
 * @return
 */
public static int count(int[] numbers) {
  int N = numbers.length;
  int cnt = 0;
  for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
      for (int k = j + 1; k < N; k++) {
        // 이 if 구문은 정확히 N(N-1)(N-2)/6 회 실행된다.
        if (numbers[i] + numbers[j] + numbers[k] == 0) {
          cnt++;
        }
      }
    }
  }
  return cnt;
}

함께 읽기

  • [[big-O-notation]]

참고문헌

  • 알고리즘 [개정4판] / 로버트 세지윅, 케빈 웨인 저/권오인 역 / 길벗 / 초판발행 2018년 12월 26일

주석

  1. 알고리즘 [개정4판]. 1.4장. 181쪽. 

  2. 알고리즘 [개정4판]. 1.4장. 205쪽. 

  3. 알고리즘 [개정4판]. 1.4장. 206쪽.