알고리즘의 점근적 분석

1. 점근적 접근 방법

Asymptotic Analysis

점근적 접근 방법 은 알고리즘의 성능이 입력 크기 n이 매우 커질 때 (무한에 가까울 때) 어떻게 변하는지를 분석하는 방법이다. 이는 작은 입력 크기에서 발생하는 미세한 차이들을 무시하고, 하드웨어, 언어 등의 특정 요인에서 벗어나 추상화하는 과정을 통해 알고리즘이 입력 크기가 커짐에 따라 성능이 어떻게 변화하는지 에 집중한다. 물론 n이 큰 경우에만 의미가 있는 한계가 있다.

2. 점근적 표기법이란?

어떤 알고리즘의 성능을 점근적으로 표기하기 위해 보통 Big-O 표기법을 사용한다.

• Big-O 표기법이란?
  • 알고리즘의 효율성을 평가하는 도구
  • 알고리즘의 실행 시간이 입력 크기에 따라 어떻게 변하는지를 나타내는 방법
  • 입력 데이터가 많아질 때 알고리즘의 소요 시간 or 메모리 사용량을 알 수 있음
  • 큰 의미로 Big-Ω, Big-Θ 표기도 내포하고 있음
• Big-O 표기법의 의의
  • 아주 정확한 실행 시간을 측정 ❌
  • 입력 크기가 커짐에 따라 시간이 어떻게 변하는지를 보는 것 ✅
  • 상수 시간이나 작은 차이를 배제하고, 입력 크기와 관련된 성능 경향 을 평가 👀
• 간단한 예시
  • O(1)
    • 상수 시간
    • 입력 크기가 얼마든지 상관없이, 항상 같은 시간이 걸림
    • 예를 들어, 배열에서 첫 번째 요소를 찾는 연산은 입력 크기와 관계없이 한 번에 끝남
  • O(n)
    • 입력 크기만큼 시간이 걸림
    • 예를 들어, 배열 안에서 특정 값을 찾기 위해 처음부터 끝까지 하나씩 비교하는 경우, 배열이 길어질수록 시간이 더 오래 걸림
  • O(log n)
    • 입력 크기가 커질수록 실행 시간이 천천히 증가
    • 예를 들어, 이진 탐색 알고리즘이 이에 해당
    • 데이터가 두 배로 늘어나도, 탐색 횟수는 조금밖에 늘어나지 않음
  • O(n²)
    • 이중 반복문처럼 입력 크기가 커지면 실행 시간이 제곱으로 증가
    • 예를 들어, 배열 안의 모든 쌍을 비교하는 알고리즘이 이에 속함

3. T(n)과 g(n)

앞으로 점근적 분석에서 알고리즘의 성능을 표현할 때는 두 함수 T(n)과 g(n)의 관계를 사용하겠다!

• T(n)
  • 입력 크기 n에 따라 알고리즘이 실행되는 실제 시간 or 실제 자원 사용량을 나타내는 함수
  • 알고리즘의 성능을 측정하는 실제 실행 시간이나 메모리 사용량
• g(n)
  • 알고리즘의 성능을 설명하기 위해 사용하는 비교 함수
  • 일반적으로는 알고리즘의 시간 복잡도 또는 공간 복잡도를 설명하기 위한 기준 함수로 사용
  • 다양한 수학적 함수(n, n^2. log n 등)로 표현

4. Big-O

• Big-O 는 상한선 을 나타내는 표기법이다.
• 즉, 알고리즘(T(n))이 특정 기준(g(n))보다 빠르게 증가하지 않는다는 것을 의미한다.
• 주로 알고리즘의 최악의 경우 성능을 평가할 때 사용된다.
• T(n), g(n)을 양의 정수 함수라고 하면, T(n) 을 런타임이라 볼 수 있다.
• T(n) 이 g(n) 보다 느리게 증가하거나, 최소한 같게 증가한다는 것을 의미하는 것!

즉, 입력 크기 n 이 커질 때

• T(n)이 g(n)보다 더 빨리 커지지 않는다.
• g(n)은 T(n)의 상한선이다.
• Big-O는 최악의 경우에도 T(n)이 g(n)보다 더 빨리 증가하지 않는다!

성립을 위한 조건은

• 상수 c 와 nₒ 가 존재해야 한다.
• c: T(n) 이 g(n) 보다 얼마나 느리게 증가할 수 있는지 나타내는 상수
• nₒ: 특정 최소 입력 크기
• 모든 n ≥ nₒ 에 대해 T(n) ≤ c * g(n) 을 만족해야 한다.
  • 즉, nₒ 이상의 입력에서는 T(n)이 g(n)보다 더 빠르게 증가하지 않아야 한다.

간단한 예시를 살펴보자

예를 들어, T(n) = 3n + 2 라는 알고리즘을 생각해보자. 이 알고리즘이 O(n) 인지 확인해보자. 우선, g(n) = n 으로 두고 T(n) = 3n + 2 가 n 보다 더 느리게 증가하는지 살펴보자.

• 상수 c 를 4로, nₒ 를 1로 설정하면,
• 모든 n ≥ 1 에서 3n + 2 ≤ 4n 이 성립한다.
• 따라서 T(n) 은 n 보다 느리게 증가하므로 T(n) = O(n) 이라고 할 수 있다.

5. Big-Ω

• Big-Ω 는 알고리즘 성능의 하한선 을 나타내는 표기법이다.
• 즉, 최소한 이 정도는 걸린다는 것을 보장해 주는 도구이다.
• 주로 알고리즘의 최적의 경우 성능을 평가할 때 사용된다.

즉, 입력 크기 n 이 커질 때

• T(n) 이 g(n) 보다 더 작거나 같은 비율로 증가한다는 뜻이다.
• T(n)을 알고리즘의 시간 복잡도라고 할 때, T(n) = Ω(g(n)) 는 T(n) 이 g(n) 보다 더 느리게 증가할 수 없다는 것을 의미한다.

성립을 위한 조건은

• 상수 c 와 nₒ 가 존재해야 한다.
• c: T(n) 이 g(n) 보다 얼마나 빠르게 증가할 수 있는지를 나타내는 상수
• nₒ: 특정 최소 입력 크기
• 모든 n ≥ nₒ 에 대해 T(n) ≥ c * g(n) 을 만족해야 한다.
  • 즉, T(n) 은 g(n) 보다 더 느리게 증가할 수 없다는 뜻!

간단한 예시를 살펴보자

예를 들어, 알고리즘의 시간 복잡도가 T(n) = 3n + 2 라고 하자. 이 알고리즘이 Ω(n) 에 속하는지 확인해보자. 여기서 g(n) = n 으로 두고 T(n) ≥ c * g(n) 을 만족하는 상수 c 와 nₒ 를 찾아보자.

• 상수 c 를 2로, nₒ 을 1로 설정하면, 모든 n ≥ 1 에서 3n + 2 ≥ 2n 이 성립한다.
• 따라서 T(n) = Ω(n) 이라고 할 수 있다.

이처럼, Big-Ω 는 T(n) 이 g(n) 보다 더 느리게 증가할 수 없다는 것을 나타내므로, 알고리즘의 최소 성능을 평가할 때 매우 유용하다. 즉, Big-Ω 표기법은 알고리즘의 성능이 이 정도 이상으로는 반드시 나온다 는 보장을 제공하는 중요한 도구이다.

6. Big-Θ

• Big-Θ 는 알고리즘 성능이 상한과 하한 모두에서 특정 함수와 같은 비율로 성장함을 나타낸다.
• 즉, 알고리즘이 입력 크기가 커짐에 따라 정확하게 어느 정도의 시간이 걸리는지를 나타내는 더 엄밀한 평가 기준이다.
• T(n)을 알고리즘의 시간 복잡도라고 할 때, T(n) = Θ(g(n)) 는 T(n)이 g(n)과 같은 비율로 증가한다는 의미이다.

즉, 입력 크기 n 이 커질 때

• T(n)이 g(n)보다 더 빠르게 증가하지 않으면서 동시에 더 느리게 증가하지 않는다는 뜻이다.

성립을 위한 조건은

• 상수 c1, c2 와 nₒ 가 존재해야 한다.
• c1: T(n)이 g(n)보다 얼마나 빠르게 증가할 수 있는지를 나타내는 상수
• c2: T(n)이 g(n)보다 얼마나 느리게 증가할 수 있는지를 나타내는 상수
• nₒ 는 특정 최소 입력 크기
• 모든 n ≥ nₒ 에 대해 c1 * g(n) ≤ T(n) ≤ c2 * g(n) 을 만족해야 한다.
  • 입력 크기 nₒ 이상의 모든 입력에서 T(n)은 g(n)과 동일한 비율로 증가해야 한다.

간단한 예시를 살펴보자

예를 들어, 알고리즘의 시간 복잡도가 T(n) = 3n + 2 라면, 이 알고리즘이 Θ(n) 에 속하는지 확인해보자. 여기서 g(n) = n 으로 가정하고, 두 상수 c1 과 c2 를 찾아보자.

• c1을 2로, c2를 4로 설정하고 nₒ을 1로 설정하면, 모든 n ≥ 1 에서 2n ≤ 3n + 2 ≤ 4n 이 성립한다.
• 따라서 T(n) = Θ(n) 이라고 할 수 있다.

이처럼, Big-Θ 알고리즘이 g(n)과 같은 속도로 증가한다는 것을 나타낸다. T(n)이 g(n)과 정확히 같은 비율로 증가할 때 Big-Θ 표기법을 사용한다. Big-Θ 는 상한선과 하한선을 모두 포함하므로, 알고리즘의 실제 성능을 정확하게 평가 하는 데 사용된다. T(n)이 g(n)과 비슷한 비율로 성장한다는 것을 보장하므로, 성능을 평가 시 더 엄격하고 명확한 기준을 제공한다.

7. 증명 예시

7-1. Big O : 함수식을 통한 T(n) = O(n²)의 증명 예시

01 : 문제

위 수식이 T(n) = O(n²) 인지 증명해보자. 결국 이 문제는 주어진 함수가 n² 보다 더 빠르게 증가하지 않는다는 것을 증명하는 과정이다. 따라서 우리는 상수 c 와 nₒ라는 상수를 찾아서 아래 부등식을 만족시키는 것이 목표이다.

이를 풀기 위해, 위처럼 우리는 주어진 함수 T(n) 의 각 항을 n²과 비교하면서 c 와 nₒ를 찾아야 한다. 주어진 함수는 총 세 개의 항으로 이루어져 있다.

• n²항 : n² 의 형태로 되어 있으므로 그대로 유지한다.
• n항 : 이 항은 n² 에 비해 작은 값이다. 이는 일정한 상수로 보정해야 한다.
• -3항 : 상수항도 입력 크기와는 상관없이 고정된 값이므로 n² 에 비해 작은 값이다.

02 : c, nₒ 찾기

상수 c 는 n²의 계수보다 크면서, n의 계수와 상수 -3을 포함할 수 있는 값이어야 한다. 예를 들어, c = 2 로 설정할 수 있다.

이젠 부등식이 성립하는 최소 nₒ를 찾아야 한다. n이 충분히 크면 n²가 n부분과 상수보다 커지므로, nₒ = 1 로 설정할 수 있다.

따라서, c = 2, nₒ = 1 일 때 아래 부등식이 성립한다.

이로써 T(n) = O(n²)임을 증명할 수 있다.

7-2. Big Θ : 함수식을 통한 T(n) = Θ(n²)의 증명 예시

01 : 문제

위 수식이 T(n) = Θ(n²) 인지 증명해보자! 이는 함수가 n² 과 정확히 같은 비율로 증가한다는 것을 보이는 문제이다. 우리는 상수 c₁ , c₂ 그리고 nₒ를 찾아서 아래 부등식이 성립하는지를 증명해야 한다.

02 : Big-O 증명

우리는 함수의 상한선을 구하기 위해 c₂와 nₒ를 찾아야 한다. 우선, 주어진 함수 T(n)이 n²보다 더 빠르게 증가하지 않는지 확인해보자.

1. 주어진 함수에서 n²항과 n항을 살펴보면, 이미 n² 형태이므로 그대로 유지된다.
2. -3n 항은 n²에 비해 작은 항이므로 이를 상수 c₂로 보정할 수 있다.

다음 부등식을 만족하는 c₂와 nₒ를 찾자.

여기서 $c_2 = 1$로 설정하면 다음 부등식이 성립한다.

이 부등식은 nₒ = 6 일 때 성립한다. n >= 6에서는 n²항이 -3n 보다 커지므로, 상한을 만족한다. 따라서, T(n) = O(n²)임을 증명할 수 있다.

03 : Big-Omega 증명

이제 하한선을 구하기 위해 c₁ 과 nₒ를 찾아보자.

이 부등식이 성립하도록 c₁ 을 구하면 된다. $c₁ = \frac{1}{3}$ 로 설정하면 다음 부등식이 성립한다:

이때도 $nₒ = 8$일 때 성립한다.$n \geq 8$에서 이 부등식이 만족된다. 따라서$T(n) = \Omega(n^2)$ 임을 증명할 수 있다.

04 : 결론

결국, 상수 $c_1 = \frac{1}{3}$, $c_2 = 1$, 그리고 $n_0 = 8$ 에서 다음 부등식이 성립한다.

따라서, 주어진 함수는 $\Theta(n^2)$임을 증명할 수 있다.

8. Reference

• https://www.geeksforgeeks.org/types-of-asymptotic-notations-in-complexity-analysis-of-algorithms/