[알고리즘] 알고리즘

반응형

 

알고리즘

알고리즘이란 어떤 입력을 받아 원하는 결과를 이끌어내는 과정을 기술한 것이다. 어떠한 문제가 주어졌을 때 이 문제를 해결하는 절차가 알고리즘이 되는 것이다. 알고리즘은 아래의 조건을 만족해야 한다.

입력 : 0개 이상의 입력이 존재해야 한다.
출력 : 1개 이상의 출력이 존재해야 한다.
명확성 : 각 명령어의 의미는 모호하지 않고 명확해야 한다.
유한성 : 유한한 단계를 거친 후 반드시 종료되어야 한다.
효율성 : 각 명령어들은 실행 가능한 연산이어야 한다.

시간 복잡도

시간 복잡도란 알고리즘의 실행 시간을 분석한 척도를 말한다. 시간 복잡도가 클 수록 알고리즘의 실행 시간이 길어진다는 뜻이다. 이 시간 복잡도는 실행에 필요한 연산의 수를 \(n\)으로 하는 함수 \(T(n)\)으로 나타낸다. 이를 시간 복잡도 함수라 한다. 아래 코드는 2 x 3을 구하는 세 가지 방법이라고 하자.

// 방법 1
result = 2 * 3;

// 방법 2
for (int i = 1; i <= 2; i++) {
    result += 3;
}

// 방법 3
for (int i = 1; i <= 2; i++) {
    for (int j = 1; j <= 3; j++) {
        result += 1;
    }
}

방법 3으로 구할 사람은 없겠지만, 방법 3이 한눈에 봐도 가장 비효율적임을 알 수 있다. 이를 분석해보자. 방법 1은 2번의 연산(곱하기 연산과 대입 연산), 방법 2는 2 x 3번의 연산, 방법 3은 2 x 3 x 3번을 연산해야한다. 수가 적어서 별로 차이가 나지 않지만, 계산에 필요한 변수가 커지면 셋의 차이는 극명하게 갈린다. 아래는 각각의 방법을 \(T(2), T(2n), T(2n^2)\)이라는 시간 복잡도 함수로 나타내고 \(n\)의 값에 따른 각 함수들의 값의 변화를 나타낸 것이다.

 

\(T(2)\)	\(T(2n)\)	\(T(2n^2)\)
2	2	2
2	4	8
2	8	32
2	16	128
2	32	512
2	64	2,048
2	128	8,192
2	256	32,768
2	512	131,072

 

위의 표를 보듯이 입력 크기가 커질수록 차이가 커짐을 알 수 있다.

점근적 표기

알고리즘의 수행시간은 입력의 크기가 충분히 크다고 생각하고 분석하는데, 이때 만들어진 함수의 증가율을 표현하는 방법을 점근적 표기법이라고 한다. \(T(n) = 2n^2 + 3n + 1\) 이 있을 때 \(n\)의 값이 충분히 크다면 \(T(n)\)은 \(n^2\)의 증가율을 따른다라는 의미이다.

 

알고리즘의 점근적 표기에서는 계수와 최고 차항을 제외하고 나머지는 무시된다. \(n\)의 수가 충분히 커진다면 계수의 영향보다 차수의 영향이 더 커지고, 최고차항의 영향이 더 커지기 때문이다. \(T(n) = n^2 + 2n + 1\) 의 경우를 생각해보자. 아래는 각각의 항들이 \(n\)의 값에 따라 어떻게 변하는지를 나타낸 것이다.

 

\(n\)	\(1\)	\(2n\)	\(n^2\)
1	1	2	1
2	1	4	4
4	1	8	16
8	1	16	64
16	1	32	256
100	1	200	10,000
10,000	1	20,000	100,000,000

 

\(T(n)\)의 값을 구했을 때, \(n\)이 10,000일 때 \(n^2\)의 값이 99.98%를 차지한다. 즉, 값이 충분히 크다면 최고차항을 고려하면 된다는 의미이다.

 

\(n\)	\(5n\)	\(2n^2\)
1	5	2
2	10	8
4	20	32
8	40	128
16	80	512
100	500	20,000
10,000	50,000	200,000,000

n이 작을 때는 계수 5와 2가 값에 영향을 주지만, n이 커지기 시작하면 결국 차수가 영향을 줌을 알 수 있다.

 

아래는 점근적 표기법 3가지를 정리한 것이다.

 

BIG-O 표기법

\(O(g(n)) = \{f(n) \mid\) 모든 \(n \ge n_0\)에 대하여 \(f(n) \le cg(n)\)인 양의 상수 \(c\)와 \(n_0\)가 존재한다\(\}\)

 

쉽게 말하면, \(O(f(n))\)은 최고차항의 차수가 \(f(n)\)과 일치하거나 더 작은 함수의 집합이다. 예를 들자면 \(O(n^2))\)은 \(n^2 + n + 1, 2n^2 + 3, 4n + 1, 99\)등을 모두 포함한다.

 

BIG-Ω 표기법

\(Ω(g(n)) = \{f(n) \mid\) 모든 \(n \ge n_0\)에 대하여 \(cg(n) \le f(n)\)인 양의 상수 \(c\)와 \(n_0\)가 존재한다\(\}\)

 

충분히 큰 \(n\)에 대해 \(g(n)\)에 상수\(c\)만 곱하면 \(g(n)\)이 더 크거나 같은 모든 함수의 집합이 \(\Omega(g(n))\)이다. \({1 \over 2}n^2, n^2logn, n^3\) 등의 함수들은 어떠한 상수를 곱하면 \(n^2\)보다 크거나 같으므로 모두 \(\Omega(n^2\))에 포함된다.

 

BIG-Θ 표기법

\(Θ(g(n)) = \{f(n) \mid\) 충분히 큰 모든 \(n\)에 대하여 \(c_1g(n) \le f(n) \le c_2g(n)\)인 양의 상수 \(c_1, c_2\)가 존재한다\(\}\)

 

다르게 말하자면, \(O(f(n))\)과 \(\Omega(f(n))\)이 둘다 성립하는 함수의 집합이 \(\Theta(g(n))\)이다.\(5n^2\)은 \(O(n^2)\)에 포함되면서도 \(\Omega(n^2)\)에도 포함되므로 \(\Theta(n^2)\)인 것이다.

 

예시)

\(2n^2 + 1\)이 \(O(n^2), \Omega(n^2), \Theta(n^2)\) 임을 보여라.

 

1. \(O(n^2)\)

상수 \(c\)를 3으로, \(n_0\)를 1로 하자.

그러면 \(2n^2 + 1\le 3n^2\)를 만족해야한다.

위의 식을 정리하면 \(1 \le n^2\)이 된다.

즉, 모든 \(n \ge n_0\)에 대해 \(1 \le n^2\)이 만족하므로, 정의를 만족하는 상수 \(c\)와 \(n_0\)가 존재한다.

따라서, \(2n^2 + 1 = O(n^2)\)이다.

 

2. \(\Omega(n^2)\)

이번에는 상수 \(c\)를 1로, \(n_0\)를 1로 하자.

그러면 \(n^2 \le 2n^2 + 1\)를 만족해야한다.

정리하면, \(-n^2 \le 1)이 된다.

즉, 모든 \(n \ge n_0\)에 대해 \(-n^2 \le 1\)이 만족하므로, 정의를 만족하는 상수 \(c\)와 \(n_0\)가 존재한다.

따라서, \(2n^2 + 1 = \Omega(n^2)\)이다.

 

3. \(\Theta(n^2)\)

1과 2에 따라 모두 만족하는 상수 \(c_1\)와\(c_2\)가 존재한다.

따라서, \(2n^2 + 1 = \Theta(n^2)\)이다.

 

 

[Reference]

문병로, 「쉽게 배우는 알고리즘」 (한빛 아카데미, 2018)

 

 

728x90