![Featured Image for [알고리즘] 점근적 분석](https://ih1.redbubble.net/image.1502642451.8092/st,small,507x507-pad,600x600,f8f8f8.jpg)
점근적 접근 방법(asymptotic analysis)은 알고리즘의 성능이 입력 크기 n이 매우 커질 때(즉, 무한에 가까울 때) 어떻게 변하는지를 분석하는 방법이다. 이는 작은 입력 크기에서 발생하는 미세한 차이들을 무시하고, 하드웨어, 언어 등의 특정 요인에서 벗어나 추상화하는 과정을 통해 알고리즘이 입력 크기가 커짐에 따라 성능이 어떻게 변화하는지에 집중한다. 점근적 분석을 통해 상수 시간이나 작은 차이를 배제하고, 입력 크기와 관련된 성능 경향을 평가할 수 있다! 물론 n이 큰 경우에만 의미가 있는 한계가 있다.
앞으로 점근적 분석에서 알고리즘의 성능을 표현할 때는 두 함수 T(n)과 g(n)의 관계를 사용하겠다!
T(n) 은 입력 크기 n에 따라 알고리즘이 실행되는 실제 시간 또는 실제 자원 사용량을 나타내는 함수다. 이것은 알고리즘의 성능을 측정하는 실제 실행 시간이나 메모리 사용량일 수 있다.
g(n) 은 알고리즘의 성능을 설명하기 위해 사용하는 비교 함수이다. 일반적으로는 알고리즘의 시간 복잡도 또는 공간 복잡도를 설명하기 위한 기준 함수로 사용되며, 이는 다양한 수학적 함수(n, n^2. log n 등)로 표현 가능하다.
그렇다면 이제 시간 복잡도에 집중해서, 알고리즘의 효율성을 표현하는 몇가지 기법을 알아보자.
T(n), g(n)을 양의 정수 함수라고 하면, 우리는 T(n) 을 런타임이라고 생각할 수 있다.
Big-O 표기법 은 알고리즘의 실행 시간이 입력 크기에 따라 어떻게 변하는지를 나타내는 방법이다. 쉽게 말해, 알고리즘의 효율성 을 평가하는 도구이다. 이를 통해 우리는 입력 데이터가 많아질 때 알고리즘이 얼마나 더 느려지거나, 메모리를 얼마나 많이 사용하는지 알 수 있다. Big-O 표기법에서 중요한 것은 정확한 실행 시간을 측정하는 것이 아니라, 입력 크기가 커짐에 따라 시간이 어떻게 변하는지를 보는 것이다. 예를 들어, O(n), O(n²), O(log n) 같은 표현을 통해 시간이 얼마나 급격히 늘어나는지를 나타낸다.
Big-O 표기법은 결국 T(n) 이 g(n) 보다 느리게 증가하거나, 최소한 같게 증가한다는 것을 의미한다. 이때 T(n) = O(g(n))은 T(n) 이 g(n) 보다 더 느리게 증가하거나, 최소한 동일한 비율로 증가한다는 의미이다. 즉, 입력 크기 n 이 커질 때, T(n)이 g(n)보다 더 빨리 커지지 않는다는 뜻이다. g(n)은 T(n)의 상한선인 셈이다. Big-O는 최악의 경우에 T(n)이 g(n)보다 더 빨리 증가하지 않는다는 것을 명시한다!!!
T(n) = O(g(n)) 라고 하기 위해서는 다음 조건을 만족해야 한다:
T(n) 이 g(n) 보다 얼마나 느리게 증가할 수 있는지를 나타내는 상수이다. nₒ 는 특정 최소 입력 크기이다.T(n) ≤ c * g(n) 을 만족해야 한다. 즉, nₒ 이상의 입력 크기에서는 T(n)이 g(n)보다 더 빠르게 증가하지 않아야 한다.O(1) : 상수 시간이다. 입력 크기가 얼마든지 상관없이, 항상 같은 시간이 걸린다. 예를 들어, 배열에서 첫 번째 요소를 찾는 연산은 입력 크기와 관계없이 한 번에 끝난다.O(n) : 입력 크기만큼 시간이 걸린다. 예를 들어, 배열 안에서 특정 값을 찾기 위해 처음부터 끝까지 하나씩 비교하는 경우, 배열이 길어질수록 시간이 더 오래 걸린다.O(log n) : 입력 크기가 커질수록 실행 시간이 천천히 증가한다. 예를 들어, 이진 탐색 알고리즘이 이에 해당한다. 데이터가 두 배로 늘어나도, 탐색 횟수는 조금밖에 늘어나지 않는다.O(n²): 이중 반복문처럼 입력 크기가 커지면 실행 시간이 제곱으로 증가한다. 예를 들어, 배열 안의 모든 쌍을 비교하는 알고리즘이 이에 속한다.예를 들어, T(n) = 3n + 2라는 알고리즘을 생각해보자. 이 알고리즘이 O(n) 인지 확인해보자. 우선, g(n) = n 으로 두고 T(n) = 3n + 2 가 n 보다 더 느리게 증가하는지 살펴보자.
nₒ 를 1로 설정하면, 모든 n ≥ 1 에서 3n + 2 ≤ 4n 이 성립한다.T(n) 은 n 보다 느리게 증가하므로 T(n) = O(n) 이라고 할 수 있다.결국, Big-O 표기법은 알고리즘이 특정 기준보다 빠르게 증가하지 않는다 는 것을 표현하는 방법이다.
알고리즘의 성능을 평가할 때, Big-Omega (Ω) 표기법은 하한선 을 나타내는 표기법이다. 즉, 최소한 이 정도는 걸린다는 것을 보장해 주는 도구이다. Big-O가 알고리즘의 실행 시간이 최대 얼마나 걸리는지를 나타낸다면, Big-Omega는 최소 얼마나 걸리는지를 표현한다. 이는 주로 알고리즘의 최적의 경우 성능을 평가할 때 사용된다.
T(n) 을 알고리즘의 시간 복잡도라고 할 때, T(n) = Ω(g(n)) 는 T(n) 이 g(n) 보다 더 느리게 증가할 수 없다는 것을 의미한다. 즉, 입력 크기 n 이 커질 때, T(n) 이 g(n) 보다 더 작거나 같은 비율로 증가한다는 뜻이다. Big-Omega 표기법을 적용하기 위해서는 다음 조건을 만족해야 한다:
nₒ 가 존재해야 한다. 여기서 c 는 T(n) 이 g(n) 보다 얼마나 빠르게 증가할 수 있는지를 나타내는 상수이다. nₒ 는 특정 최소 입력 크기이다.n ≥ nₒ 에 대해 T(n) ≥ c * g(n) 을 만족해야 한다. 즉, T(n) 은 g(n) 보다 더 느리게 증가할 수 없다는 뜻이다.Big-Omega 는 알고리즘의 최소 성능 을 보장하므로, 최적의 경우 에 알고리즘이 얼마나 빠르게 동작할 수 있는지를 나타낸다. 이를 통해 우리는 최선의 상황에서 알고리즘이 얼마나 성능을 발휘할 수 있는지 알 수 있다.
예를 들어, 알고리즘의 시간 복잡도가 T(n) = 3n + 2 라고 하자. 이 알고리즘이 Ω(n) 에 속하는지 확인해보자. 여기서 g(n) = n 으로 두고 T(n) ≥ c * g(n) 을 만족하는 상수 c 와 nₒ 를 찾아보자.
nₒ 을 1로 설정하면, 모든 n ≥ 1 에서 3n + 2 ≥ 2n 이 성립한다.T(n) = Ω(n) 이라고 할 수 있다.이처럼, Big-Omega 는 T(n) 이 g(n) 보다 더 느리게 증가할 수 없다는 것을 나타내므로, 알고리즘의 최소 성능을 평가할 때 매우 유용하다. 즉, Big-Omega 표기법은 알고리즘의 성능이 이 정도 이상으로는 반드시 나온다 는 보장을 제공하는 중요한 도구이다.
알고리즘의 성능을 나타내는 또 다른 중요한 표기법은 Big-Theta (Θ) 표기법이다. Big-O 표기법이 성능의 상한, Big-Omega (Ω) 하한을 나타낸다면, Big-Theta 는 알고리즘의 성능이 상한과 하한 모두에서 특정 함수와 같은 비율로 성장함을 나타낸다. 즉, 알고리즘이 입력 크기가 커짐에 따라 정확하게 어느 정도의 시간이 걸리는지를 나타내는 더 엄밀한 평가 기준이다.
T(n)을 알고리즘의 시간 복잡도라고 할 때, T(n) = Θ(g(n)) 는 T(n)이 g(n)과 같은 비율로 증가한다는 의미이다. 즉, 입력 크기 n 이 커질수록 T(n)이 g(n)보다 더 빠르게 증가하지 않으면서 동시에 더 느리게 증가하지 않는다는 뜻이다. Big-Theta 표기법을 적용하기 위해서는 다음 두 가지 조건을 만족해야 한다:
nₒ 가 존재해야 한다. 여기서 c1 과 c2 는 T(n)이 g(n)보다 얼마나 빠르게 또는 느리게 증가할 수 있는지를 나타내는 상수이다. nₒ 는 특정 최소 입력 크기이다.n ≥ nₒ 에 대해 c1 * g(n) ≤ T(n) ≤ c2 * g(n) 을 만족해야 한다. 즉, 입력 크기 nₒ 이상의 모든 입력에서 T(n)은 g(n)과 동일한 비율로 증가해야 한다.Big-Theta 는 상한선과 하한선을 모두 포함하므로, 알고리즘의 실제 성능을 정확하게 평가 하는 데 사용된다. T(n)이 g(n)과 비슷한 비율로 성장한다는 것을 보장하므로, 성능을 평가할 때 Big-Theta는 더 엄격하고 명확한 기준을 제공한다.
예를 들어, 알고리즘의 시간 복잡도가 T(n) = 3n + 2 라면, 이 알고리즘이 Θ(n) 에 속하는지 확인해보자. 여기서 g(n) = n으로 가정하고, 두 상수 c1과 c2를 찾아보자.
이처럼, Big-Theta는 알고리즘이 g(n)과 같은 속도로 증가한다는 것을 나타낸다. T(n)이 g(n)과 정확히 같은 비율로 증가할 때 Big-Theta 표기법을 사용한다.
$$ \frac{3}{2}n^2 + \frac{5}{2}n - 3 \leq O(n^2) $$
위 수식이 T(n) = O(n²) 인지 증명해보자. 결국 이 문제는 주어진 함수가 n² 보다 더 빠르게 증가하지 않는다는 것을 증명하는 과정이다. 따라서 우리는 상수 c 와 nₒ라는 상수를 찾아서 아래 부등식을 만족시키는 것이 목표이다.
$$ T(n) \leq c \cdot n^2 \quad \text{(for } n \geq n_0) $$
이를 풀기 위해, 위처럼 우리는 주어진 함수 T(n) 의 각 항을 n²과 비교하면서 c 와 nₒ를 찾아야 한다. 주어진 함수는 총 세 개의 항으로 이루어져 있다:
n²항 : n² 의 형태로 되어 있으므로 그대로 유지한다.n항 : 이 항은 n² 에 비해 작은 값이다. 이는 일정한 상수로 보정해야 한다.-3항 : 상수항도 입력 크기와는 상관없이 고정된 값이므로 n² 에 비해 작은 값이다.$$ \frac{3}{2}n^2 + \frac{5}{2}n - 3 \leq 2n^2 $$
상수 c 는 n²의 계수보다 크면서, n의 계수와 상수 -3을 포함할 수 있는 값이어야 한다. 예를 들어, c = 2 로 설정할 수 있다.
이젠 부등식이 성립하는 최소 nₒ를 찾아야 한다. n이 충분히 크면 n²가 n부분과 상수보다 커지므로, nₒ = 1 로 설정할 수 있다.
따라서, c = 2, nₒ = 1 일 때 아래 부등식이 성립한다.
$$ T(n) = \frac{3}{2}n^2 + \frac{5}{2}n - 3 \leq 2n^2 \quad \text{for } n \geq 1 $$
이로써 T(n) = O(n²)임을 증명할 수 있다.
$$ \frac{1}{2}n^2 - 3n = \Theta(n^2) $$
위 수식이 T(n) = Θ(n²) 인지 증명해보자! 이는 함수가 n² 과 정확히 같은 비율로 증가한다는 것을 보이는 문제이다. 우리는 상수 c₁ , c₂ 그리고 nₒ를 찾아서 아래 부등식이 성립하는지를 증명해야 한다.
$$ c_1 n^2 \leq \frac{1}{2}n^2 - 3n \leq c_2 n^2 \quad \text{(for } n \geq n_0) $$
우리는 함수의 상한선을 구하기 위해 c₂와 nₒ를 찾아야 한다. 우선, 주어진 함수 T(n)이 n²보다 더 빠르게 증가하지 않는지 확인해보자.
n²항과 n항을 살펴보면, 이미 n² 형태이므로 그대로 유지된다.-3n 항은 n²에 비해 작은 항이므로 이를 상수 c₂로 보정할 수 있다.다음 부등식을 만족하는 c₂와 nₒ를 찾자.
$$ \frac{1}{2}n^2 - 3n \leq c_2 n^2 $$
여기서 $ c_2 = 1 $로 설정하면 다음 부등식이 성립한다:
$$ \frac{1}{2}n^2 - 3n \leq n^2 $$
이 부등식은 nₒ = 6 일 때 성립한다. n >= 6에서는 n²항이 -3n 보다 커지므로, 상한을 만족한다. 따라서, T(n) = O(n²)임을 증명할 수 있다.
이제 하한선을 구하기 위해 c₁ 과 nₒ를 찾아보자.
$$ c_1 n^2 \leq \frac{1}{2}n^2 - 3n $$
이 부등식이 성립하도록 c₁ 을 구하면 된다. $c₁ = \frac{1}{3}$ 로 설정하면 다음 부등식이 성립한다:
$$ \frac{1}{3}n^2 \leq \frac{1}{2}n^2 - 3n $$
이때도 $nₒ = 8$ 일 때 성립한다. $n \geq 8$ 에서 이 부등식이 만족된다. 따라서 $T(n) = \Omega(n^2)$ 임을 증명할 수 있다.
결국, 상수 $c_1 = \frac{1}{3}$, $c_2 = 1$, 그리고 $n_0 = 8$ 에서 다음 부등식이 성립한다.
$$ \frac{1}{3}n^2 \leq \frac{1}{2}n^2 - 3n \leq n^2 \quad \text{(for } n \geq 8) $$
따라서, 주어진 함수는 $ \Theta(n^2) $임을 증명할 수 있다.