Asymptotic Analysis
점근적 접근 방법 은 알고리즘의 성능이 입력 크기 n이 매우 커질 때 (무한에 가까울 때) 어떻게 변하는지를 분석하는 방법이다. 이는 작은 입력 크기에서 발생하는 미세한 차이들을 무시하고, 하드웨어, 언어 등의 특정 요인에서 벗어나 추상화하는 과정을 통해 알고리즘이 입력 크기가 커짐에 따라 성능이 어떻게 변화하는지 에 집중한다. 물론 n이 큰 경우에만 의미가 있는 한계가 있다.
어떤 알고리즘의 성능을 점근적으로 표기하기 위해 보통 Big-O 표기법을 사용한다.
Big-O 표기법이란?
Big-Ω, Big-Θ 표기도 내포하고 있음Big-O 표기법의 의의
성능 경향 을 평가 👀간단한 예시
O(1)
O(n)
O(log n)
O(n²)
T(n)과 g(n)앞으로 점근적 분석에서 알고리즘의 성능을 표현할 때는 두 함수 T(n)과 g(n)의 관계를 사용하겠다!
T(n)
n에 따라 알고리즘이 실행되는 실제 시간 or 실제 자원 사용량을 나타내는 함수g(n)
n, n^2. log n 등)로 표현$$ T(n) = O(g(n)) $$
T(n))이 특정 기준(g(n))보다 빠르게 증가하지 않는다는 것을 의미한다.T(n), g(n)을 양의 정수 함수라고 하면, T(n) 을 런타임이라 볼 수 있다.T(n) 이 g(n) 보다 느리게 증가하거나, 최소한 같게 증가한다는 것을 의미하는 것!n 이 커질 때T(n)이 g(n)보다 더 빨리 커지지 않는다.g(n)은 T(n)의 상한선이다.T(n)이 g(n)보다 더 빨리 증가하지 않는다!T(n) 이 g(n) 보다 얼마나 느리게 증가할 수 있는지 나타내는 상수T(n) ≤ c * g(n) 을 만족해야 한다.
T(n)이 g(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) 이라고 할 수 있다.$$ T(n) = Ω(g(n)) $$
n 이 커질 때T(n) 이 g(n) 보다 더 작거나 같은 비율로 증가한다는 뜻이다.T(n)을 알고리즘의 시간 복잡도라고 할 때, T(n) = Ω(g(n)) 는 T(n) 이 g(n) 보다 더 느리게 증가할 수 없다는 것을 의미한다.nₒ 가 존재해야 한다.T(n) 이 g(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ₒ 를 찾아보자.
nₒ 을 1로 설정하면, 모든 n ≥ 1 에서 3n + 2 ≥ 2n 이 성립한다.T(n) = Ω(n) 이라고 할 수 있다.이처럼, Big-Ω 는 T(n) 이 g(n) 보다 더 느리게 증가할 수 없다는 것을 나타내므로, 알고리즘의 최소 성능을 평가할 때 매우 유용하다. 즉, Big-Ω 표기법은 알고리즘의 성능이 이 정도 이상으로는 반드시 나온다 는 보장을 제공하는 중요한 도구이다.
$$ T(n) = Θ(g(n)) $$
T(n)을 알고리즘의 시간 복잡도라고 할 때, T(n) = Θ(g(n)) 는 T(n)이 g(n)과 같은 비율로 증가한다는 의미이다.n 이 커질 때T(n)이 g(n)보다 더 빠르게 증가하지 않으면서 동시에 더 느리게 증가하지 않는다는 뜻이다.nₒ 가 존재해야 한다.T(n)이 g(n)보다 얼마나 빠르게 증가할 수 있는지를 나타내는 상수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 를 찾아보자.
n ≥ 1 에서 2n ≤ 3n + 2 ≤ 4n 이 성립한다.T(n) = Θ(n) 이라고 할 수 있다.이처럼, Big-Θ 알고리즘이 g(n)과 같은 속도로 증가한다는 것을 나타낸다. T(n)이 g(n)과 정확히 같은 비율로 증가할 때 Big-Θ 표기법을 사용한다. Big-Θ 는 상한선과 하한선을 모두 포함하므로, 알고리즘의 실제 성능을 정확하게 평가 하는 데 사용된다. T(n)이 g(n)과 비슷한 비율로 성장한다는 것을 보장하므로, 성능을 평가 시 더 엄격하고 명확한 기준을 제공한다.
$$ \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) $임을 증명할 수 있다.