Big-O 표기법

Big-O 표기법에 대한 설명은 알고리즘의 효율을 측정하고 비교하는 방법을 이해하는 데 중요한 개념입니다. 강의록을 한 줄 한 줄 분석하여 자세하게 정리해드리겠습니다.

알고리즘 효율 측정 방법

1. 알고리즘의 효율을 측정하려면?

   • 알고리즘의 성능을 평가하고, 서로 다른 알고리즘을 비교하는 것이 중요합니다.

2. 두 알고리즘 A와 B를 비교하려면:

   • 방법 1) "조금, 많이 빠르다" 같은 애매한 표현:
     • 성능 비교가 애매하고 명확하지 않기 때문에 객관적이지 않습니다.
   • 방법 2) 프로그램을 만들어 실행 속도 비교:
     • 이 방법은 사용된 컴퓨터의 성능, 운영체제, 실행 환경 등에 따라 결과가 달라질 수 있습니다.
   • 문제점 3) 입력 크기 변화에 따른 성능 차이:
     • 입력 크기(데이터의 양)가 작을 때와 클 때의 성능 차이가 확연히 다를 수 있습니다. 이 때문에 동일한 입력 크기에서는 알고리즘이 효율적이지만, 입력이 커지면 성능 차이가 커질 수 있습니다.

3. 대안으로 Big-O 표기법 사용:

   • 이러한 문제를 해결하기 위해 Big-O 표기법을 사용합니다. Big-O 표기법은 알고리즘의 성능을 입력 크기(N)의 함수로 표현하여, 입력이 커짐에 따라 성능이 어떻게 변하는지를 나타냅니다.

Big-O 표기법의 단계적 설명

BIG-O 표기법 1단계: 대략적인 계산

• 수행되는 연산(산술, 비교, 대입 등)의 개수를 대략적으로 판단합니다.
  • 예를 들어, 알고리즘에서 수행되는 연산의 횟수가 다음과 같다면:
    • $1$ : 상수 시간이 걸리는 연산
    • $N + 1$ : 입력 크기 N에 따라 선형적으로 증가하는 연산
    • $N^2 + 1$ : 입력 크기 N에 따라 제곱에 비례하여 증가하는 연산

BIG-O 표기법 2단계: "대장만 남긴다" (가장 큰 영향 요소만 남김)

• 규칙 1) 영향력이 가장 큰 대표 항목만 남기고 삭제
  • 복잡도에서 가장 중요한 항목(즉, 가장 큰 성장률을 가지는 항목)만 남기고 나머지는 무시합니다.
• 규칙 2) 상수 무시
  • 상수는 입력 크기가 커질수록 상대적으로 영향이 작아지므로 무시합니다.
  • 예: $O(1 + N + 4 + N^2 + 1)$
    • 먼저 가장 큰 항목을 제외하고 나머지 항목은 무시합니다:
      $= O(N^2)$
    • 이후 상수를 무시합니다:
      $= O(N^2)$

Big-O 표기법의 의미

• 입력 N의 크기에 따라 성능에 영향을 받는 정도를 나타냅니다.
  • Big-O 표기법은 알고리즘이 입력 크기 N이 커짐에 따라 얼마나 더 많은 자원(시간, 메모리 등)을 사용하는지를 나타냅니다.
  • 예를 들어, O(N)은 입력 크기에 선형적으로 비례하여 시간이 증가함을 의미하고, O(N^2)은 제곱에 비례하여 시간이 증가함을 의미합니다.

로그 함수 (Logarithm)

로그 함수는 Big-O 표기법에서 자주 등장하는 개념입니다.

1. 로그arithm의 기본 개념:

   • $2^1 = 2$
     • 2의 1제곱은 2입니다.
   • $2^2 = 4$
     • 2의 2제곱은 4입니다.
   • $2^3 = 8$
     • 2의 3제곱은 8입니다.

2. 로그의 정의:

   • $a^? = b$라는 식에서 ?를 구하려면, $? = log_a(b)$가 됩니다.
     • 예를 들어, $2^? = N$일 때 ?는 $log_2(N)$입니다.
     • 이는 "2를 몇 번 곱해야 $N$이 되는가?"라는 의미를 가집니다.