[알고리즘] 알고리즘과 빅오(Big-Oh)

 

 

 

 

 

 

🧐 알고리즘?

어떤 문제를 풀기 위한 유한한 절차와 방법을 의미합니다.

 

위 정의에서의 '문제'는 보통 입력값이 동일한 경우 출력값이 동일한(= 수학적으로 엄밀히 정의된) 문제를 의미합니다.

 

 

 

 

절차와 방법?

저희는 계산 문제를 풀 때 숫자와 사칙연산을 이용하여 문제를 풀이하는 것 처럼

컴퓨터로 계산 문제를 풀기 위해서는 컴퓨터에 주어진 명령어 집합(instruction set)을 이용하여 풀이합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 알고리즘의 성능 분석

알고리즘의 성능을 분석하는 방법으로는 실제로 시작시간과 종료시간을 측정하여 분석하는 실험적 분석과,

이론적으로 기술하여 성능을 측정하는 이론적 분석 방법이 있습니다.

 

 

실험적 분석은 때때로 유용하지만, 다양한 외부 요인들(예를 들어, 컴퓨터의 하드웨어 사양)에 의해 성능을 정확하게 분석할 수 없다는 단점이 있습니다.

 

 

이론적 분석 방법은 앞으로 살펴볼 방법으로, 알고리즘의 성능을 실제 구현을 통해서가 아닌 이론적으로 분석하여 기술하는 방법입니다.

 

이론적 분석에서는 보통 입력의 크기를 n이라 표기하고, 소요시간을 n에 관한 함수로 표현합니다.

 

이를 통해 외부 요인들과 독립적으로 알고리즘의 성능을 표현할 수 있고 비교할 수 있습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 시간 복잡도 (Time Complexity)

이론적 분석을 통해 구한 알고리즘의 수행 시간을 시간 복잡도라고 합니다.

 

 

이론적 분석에서 고려되는 기본 연산(단일 연산)들은 다음과 같습니다.

• 숫자를 변수에 대입한다.
• 함수를 호출하고, 함수의 결과값을 반환한다.
• 두 (작은) 정수 사이의 사칙 연산.
• 배열(Array)의 get, set 연산.
• 기타 컴퓨터 하드웨어에서 정의된 단일 명령어.

 

한 번의 기본 연산을 수행하는데 걸리는 시간은 외부 요인에 따라 달라지므로 정확하게는 구할 수 없습니다.

 

그러나 각각의 단일 연산들은 입력 크기와는 무관한 시간이 소용됩니다.

 

이론적으로 이러한 연산들은 상수 시간이 소모된다고 고려한 후 분석을 진행합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 시간 복잡도와 성능

이론적 분석에서는 입력 사이즈가 커진다면 이에 비례해서 함수의 수행 속도가 어느 정도로 증가되는지에 관심이 있습니다.

 

위에서 살펴본 기본 연산(단일 연산)들은 상수 시간이 소모되므로, 입력 사이즈와 무관할 뿐더러 함수가 증가하는 속도에도 거의 영향을 끼치지 않습니다.

(물론 속도의 차이는 존재할 수 있지만 그 영향이 매우 의미없을 정도로 작기 때문에 영향이 없다고 보아도 무방합니다)

 

 

 

 

이해를 돕기 위해 다음 예시를 살펴보도록 하겠습니다.

 

 

컴퓨터 A와, A보다 모든 기본 연산들의 성능이 10배 빠른 컴퓨터 B가 존재합니다.

시간 복잡도 ( n = 입력의 크기 )	컴퓨터 A가 k개의 자료를 처리하는 동안, B가 처리할 수 있는 자료의 수
$n$	$10k$
$n^3$	약  $2k$
$2^n$	약  $k + 3$

 

 

시간 복잡도가 $n^3$ 인 경우 $10 \approx 2^3 $이므로 $2k$ 이며,

$2^n$인 경우 $log_2(10) \approx 3$이므로 $k+3$ 입니다.

 

 

이해가 어렵다면 다음과 같은 방법으로 구할 수도 있습니다.

 

 

 

중요한 것은 알고리즘이 복잡할수록(= 시간 복잡도가 증가할수록) 기본 연산들의 속도 차이는 거의 무의미해진다는 것입니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐  빅오(Big - Oh) 표기법

$f(n)$ 과 $g(n)$ 을 자연수에서 실수로의 함수라고 할 때,

모든 $n > n_0$에 대하여
$$f(n) \leq c \cdot g(n)$$
을 만족하는 어떤 실수  $c > 0$ 과,  자연수  $n_0 > 0$ 가 존재하는 경우

 $f(n) = O(g(n))$ ( $f(n)$   is big-oh of (order) $ g(n)$ ) 라 합니다.

 

수식을 풀어서 설명하자면

 

특정한 입력의 크기($n_0$)보다 큰 모든 입력에 대하여 $f(n)$ 이상의 시간이 소요되는 $c \cdot g(n)$이 존재하는 경우,

 

$f(n) = O(g(n))$ 이라 표현할 수 있습니다.

 

 

그림으로 표현

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐  빅오(Big - Oh) 표기법의 규칙

 

우선 빅오 표기법은 반드시 제일 간략한 형태로 표현하여야 합니다.

 

 

 

 

제일 간략한 형태? 🫤

모든 계수(coefficient)가 1인 함수들 중 가능한 가장 증가율이 작은 함수를 의미합니다.

 

 

👉  최고차항이 $x$ 인 어떠한 다항식 $f(n) = a_0 + a_1 n + a_2 n^2 + ... + a_x n^x$ 에 대하여,

$f(n) = O(n^x)$ 입니다.

 

 

 

1. 함수의 각 항(term)의 계수(coefficient)는 생략 가능합니다. (ex: $13n^2 = O(n^2)$)

 

 

2. $a > b$ 일 때,  $n^a$ 와 $n^b$ 의 항이 같이 있다면,  $n^a$ 항만 남길 수 있습니다.

• 이 경우 $n^a$ dominate $n^b$ 이라 합니다.
• ex:  $f(n) = n^4 + n^3 = O(n^4)$

 

 

3. 모든 exponential(지수) term은, polynomial(다항식) term을 dominate 합니다.

• 로그를 씌워 쉽게 확인 가능합니다.
• ex:   $1.0000001^{n}$   dominate   $n^{100000000}$

 

 

4. 모든 polynomial term은 logarithm(로그) term을 dominate 합니다.

• ex:   ${n}$   dominate   $(log\;n)^{100000000}$

 

 

또한 로그 베이스는 쉽게 바꿀 수 있으므로 전혀 상관이 없으며, 기본적으로 베이스는 생략하고 작성합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

빅오 표기법 예시 👀

 

1. $f(n) = 30$ 일 때, $f(n)$ 의 시간 복잡도를 빅오 표기법을 이용하여 나타내시오.

 

풀이 👇

$c=100$, $g(n) = 1$ 이라 둘 경우, $1(= n_0$) 보다 큰 모든 자연수에서 $f(n) \leq c \cdot g(n)$ 이므로

$$f(n) = O(1)$$

 

이를 통해 모든 상수 함수는 $O(1)$ 의 시간 복잡도를 가진다는 것을 알 수 있습니다.

즉 컴퓨터의 하드웨어 스펙에 관계없이 모든 컴퓨터의 기본 연산들은 $O(1)$ 의 시간이 소요됩니다.

 

 

 

 

 

2. $f(n) = 3n + 1000$ 일 때, $f(n)$ 의 시간 복잡도를 빅오 표기법을 이용하여 나타내시오.

 

풀이 👇

$c = 4$, $g(n) = n$ 이라 둘 경우, $1000(=n_0)$ 보다 큰 모든 자연수에서 $f(n) \leq c \cdot g(n)$ 이므로

$$f(n) = O(n)$$

 

 

 

 

 

 

3. $f(n) = 3n^{2} -4n + 2 $ 일 때, $f(n)$ 의 시간 복잡도를 빅오 표기법을 이용하여 나타내시오.

 

풀이 👇

$c = 10000$, $g(n) = n^{2}$ 이라 둘 경우, $1(=n_0)$ 보다 큰 모든 자연수에서 $f(n) \leq c \cdot g(n)$ 이므로

$$f(n) = O(n^2)$$

 

 

 

 

 

 

 

4. $f(n) = 100n^{3} + 10n log n + 2 $ 일 때, $f(n)$ 의 시간 복잡도를 빅오 표기법을 이용하여 나타내시오.

 

풀이 👇

$c = 10000$, $g(n) = n^{3}$ 이라 둘 경우, $1(=n_0)$ 보다 큰 모든 자연수에서 $f(n) \leq c \cdot g(n)$ 이므로

$$f(n) = O(n^3)$$

 

 

 

 

 

 

 

5. $f(n) = log n + 2 log log n - 3 $ 일 때, $f(n)$ 의 시간 복잡도를 빅오 표기법을 이용하여 나타내시오.

 

풀이 👇

$c = 10000$, $g(n) = log n$ 이라 둘 경우, $1(=n_0)$ 보다 큰 모든 자연수에서 $f(n) \leq c \cdot g(n)$ 이므로

$$f(n) = O(log n)$$

 

* $log n$이 $log log n$을 doninate 합니다. *

 

 

 

 

 

6. $ f(n) = 2^{n+2}$ 일 때, $f(n)$ 의 시간 복잡도를 빅오 표기법을 이용하여 나타내시오.

 

풀이 👇

$c = 5$, $g(n) = 2^n$ 이라 둘 경우, $1(=n_0)$ 보다 큰 모든 자연수에서 $f(n) \leq c \cdot g(n)$ 이므로

$$f(n) = O(2^n)$$

 

* 지수함수의 베이스는 건들면 안됩니다. *

 

 

 

 

 

7. $ f(n) = n! $ 일 때, $f(n)$ 의 시간 복잡도를 빅오 표기법을 이용하여 나타내시오.

 

👉 $O(n^{n})$

(상식적으로 알아는 두세용 :) )

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐  빅오(Big - Oh) 표기법을 사용한 알고리즘의 성능 비교법

 

두 알고리즘을 빅오 표기법을 사용하여 이론적으로 비교할 수 있습니다.

 

1. 두 알고리즘의 기본 연산의 수를 입력 크기에 대한 함수로 표현합니다.

 

2. 1번의 함수를 빅오 표기법으로 표현합니다.

 

3. 빅오 표기법 안의 두 함수를 비교하여, 더 느리게 증가하는 함수로 표현 가능 알고리즘이 이론적으로 더 좋은 알고리즘입니다.

• 물론 입력의 크기가 작은 경우 더 효율적인 알고리즘이 있을 수 있으나, 이론적인 분석에서는 일반적으로 빅오를 기준으로만 비교합니다.

 

 

아래는 예시입니다.

 

 

 

 

 

 

 

 

 

 

 

 

🧐 빅 오메가

$f(n)$ 과 $g(n)$ 을 자연수에서 실수로의 함수라고 할 때,

모든 $n > n_0$에 대하여
$$g(n) \geq c \cdot f(n)$$
을 만족하는 어떤 실수 $c > 0$ 과, 자연수 $n_0 > 0$가 존재하는 경우 $$g(n) = \Omega(f(n))$$ 라 합니다.

 

 

정의에 의해 어떤 두 함수 $f(n)$, $  g(n)$ 에 대하여, $f(n) = O(g(n))$ 을 만족하면 $g(n) = \Omega(f(n))$ 를 만족합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 빅 세타

$f(n) = O(g(n))$ 임과 동시에
$g(n) = O(f(n))$ 이면

$$f = \Theta(g(n)) \; , \;\;\; g = \Theta(f(n))$$ 입니다.

 

정확히는 다음과 같습니다.

 

$f(n)$ 과 $g(n)$ 을 자연수에서 실수로의 함수라고 할 때,

모든 $n > n_0$에 대하여
$$c_1 \cdot f(n) \leq g(n) \leq c_2 \cdot f(n)$$
을 만족하는 어떤 실수  $c_1,\; c_2 > 0$ 과, 자연수 $n_0 > 0$가 존재하는 경우
 
$$f = \Theta(g(n)) \; , \;\;\; g = \Theta(f(n))$$라 합니다.

 

 

 

 

 

 

빅오메가, 빅세타 표기법 예시 👀

 

1. $f_1(n) = 2n + 20$  과  $f_2(n) = n^{2} $ 비교

 

풀이 👇

$f_1(n) = O(f_2(n))$ 이므로 $f_2(n) = \Omega(f_1(n))$ 입니다.

 

그러나 $f_1(n) = \Theta(f_2(n))$ 은 아닙니다.

 

 

 

 

2. $f_1(n) = 2n $  과  $f_2(n) = 100n $ 비교

 

풀이 👇

$c = \frac{1}{50}$,  $n_0 = 1$로 둔다면, 모든 자연수 $n \geq n_0$ 에 대하여  $f_1(n) \leq c \cdot f_2(n)$ 입니다.

 

즉 $f_1(n) = O(f_2(n))$ 입니다.

 

$c = 50$,  $n_0 = 1$로 둔다면, 모든 자연수 $n \geq n_0$ 에 대하여  $f_2(n) \leq c \cdot f_1(n)$ 입니다.

 

즉 $f_2(n) = O(f_1(n))$ 입니다.

 

따라서 $f_1(n) = \Theta(f_2(n))$ 이며,  $f_2(n) = \Theta(f_1(n))$ 입니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 리틀 오 (little - oh)

리틀 오는 빅오와 비슷합니다.

 

빅오는 같거나 더 빠르게 동작함을 표현하였다면,

리틀 오는 특정 크기의 입력 이상의 모든 상황에서 $f(n)$ 이 $g(n)$ 보다 무조건 빠름을 표현합니다.

 

두 함수 $f(n)$, $g(n)$에 대하여, 

모든 실수 $c > 0$ 와, $n_0 > 0 $인 어떠한 $n_0$ 에 대하여, 

$n > n_0$ 을 만족하는 모든 n에 대하여
$$f(n) < c \cdot g(n)$$인 경우, 

$$f(n) = o(g(n))$$

이라 표현합니다.

 

 

 

보통 $f(n)$ 이 $g(n)$ 에 의해 억눌린다 ( $f(n)$ is dominated by $g(n)$ )고 표현하는 경우,

$f(n) = o(g(n))$ 을 의미합니다.

 

 

주의할 점은 모든 실수 c에 대해 성립하여야 하며, $n_0$ 의 경우 특정한 하나의 $n_0$ 만 존재하여도 된다는 것입니다.

 

 

 

 

 

 

 

 

 

 

 

리틀 오 표기법 예시 👀

 

 

$f_1(n) = 2n $ , $f_2(n) = 100n $ 인 경우

 

1. $f_1(n) = o(f_2(n))$ 인가?

 

풀이 👇

$c =\frac{1}{100}$ 인 경우, 항상 $f_1(n) \geq c \cdot f_2(n)$ 입니다.

 

즉 $f_1(n) = o(f_2(n))$ 가 아닙니다.

 

 

 

 

2. $f_2(n) = o(f_1(n))$ 인가?

 

풀이 👇

$ c = 1 $ 인 경우, 항상 $f_2(n) \geq c \cdot f_1(n)$ 입니다.

 

즉 $f_2(n) = o(f_1(n))$ 가 아닙니다.

 

 

 

 

 

 

 

$f_1(n) = n^2 $ , $f_2(n) = 100n $ 인 경우

 

 

1. $f_2(n) = o(f_1(n))$ 인가?

 

풀이 👇

이 경우 어떠한 c를 잡아도 $n_0 = \frac{200}{c}$ 로 두는 경우 모든 $n > n_0$ 에 대하여, $f_2(n) < c \cdot f_1(n)$ 을 만족합니다.

 

즉 $f_2(n) = o(f_1(n))$ 가 맞습니다.

 

 

 

 

 

 

 

 

 

 

 

✔️ 표기법 정리

 

🧐  빅오(Big - Oh) 표기법

$f(n)$ 과 $g(n)$ 을 자연수에서 실수로의 함수라고 할 때,

모든 $n > n_0$에 대하여
$$f(n) \leq c \cdot g(n)$$
을 만족하는 어떤 실수  $c > 0$ 과,  자연수  $n_0 > 0$ 가 존재하는 경우

 $f(n) = O(g(n))$ ( $f(n)$   is big-oh of (order) $ g(n)$ ) 라 합니다.

 

 

 

 

 

 

🧐 빅 오메가

$f(n)$ 과 $g(n)$ 을 자연수에서 실수로의 함수라고 할 때,

모든 $n > n_0$에 대하여
$$g(n) \geq c \cdot f(n)$$
을 만족하는 어떤 실수 $c > 0$ 과, 자연수 $n_0 > 0$가 존재하는 경우 $$g(n) = \Omega(f(n))$$ 라 합니다.

 

 

 

 

 

 

🧐 빅 세타

$f(n) = O(g(n))$ 임과 동시에
$g(n) = O(f(n))$ 이면

$$f = \Theta(g(n)) \; , \;\;\; g = \Theta(f(n))$$ 입니다.

 

정확히는 다음과 같습니다.

 

$f(n)$ 과 $g(n)$ 을 자연수에서 실수로의 함수라고 할 때,

모든 $n > n_0$에 대하여
$$c_1 \cdot f(n) \leq g(n) \leq c_2 \cdot f(n)$$
을 만족하는 어떤 실수  $c_1,\; c_2 > 0$ 과, 자연수 $n_0 > 0$가 존재하는 경우
 
$$f = \Theta(g(n)) \; , \;\;\; g = \Theta(f(n))$$라 합니다.

 

 

 

 

 

 

🧐 리틀 오 (little - oh)

두 함수 $f(n)$, $g(n)$에 대하여, 

모든 실수 $c > 0$ 와, $n_0 > 0 $인 어떠한 $n_0$ 에 대하여, 

$n > n_0$ 을 만족하는 모든 n에 대하여
$$f(n) < c \cdot g(n)$$인 경우, 

$$f(n) = o(g(n))$$

이라 표현합니다.