Big-O표기법이란?
- 컴퓨터 공학에서 알고리즘의 복잡도 또는 성능을 표현하기 위해 사용되며 최악의 경우를 표현한다.
- 알고리즘 실행시간이나, 사용메모리 공간을 표현하기도 한다.
- 공간 복잡도 : 시간뿐만 아니라 메모리(혹은 공간)또한 신경써야 한다.
- 상수항은 무시한다.
- Big-O : 시간의 상한을 나타낸다.
- Big-θ(빅 세타) : 등가 개념 혹은 하한을 나타낸다.
- Big-Ω (빅 오메가) : 세타는 O와 오메가를 모두 의미한다. 수행시간이 O(N)이면서 Ω(N)이라면 이 알고리즘의 수행시간을 θ(N)이라고 표현
예를 들어, n개의 자연수를 병합 정렬로 정렬하기 위해서는 'O(n)의 시간이 소요된다' 라고 표현한다.
지배적이지 않은 항은 무시하라.
- 상수항을 무시한다면 O(N^2 + N^2) 는 O(N^2)이 된다. 그보다 더 작은 N은 무 시된다.
- O(N^2 +N)은 O(N^2)
- O(N + logN) 은 O(N)
- O(5*2^N + 10000N^100)은 O(2^N)이 된다.
- O(B^2 + A)의 경우는 하나의 항으로 줄일 수 없다. B와 A사이의 특별한 관계를 알 수 없기 때문이다.
알고리즘 : 덧셈 vs 곱셈
- "A 일을 모두 끝마친 후에 B 일을 수행하라"의 형태라면 A와 B의 수행시간을 더해야 한다.
- "A 일을 할 때마다 B일을 수행하라"의 형태라 면 A와 B의 수행시간을 곱해야 한다.
O(1)
O(1) 은 알고리즘의 실행시간이 입력되는 데이터의 크기에 상관없이 항상 같을 경우를 의미
bool IsFirstElementNull(String[] strings)
{
if(strings[0] == null)
{
return true;
}
return false;
}
O(N)
O(N) 는 입력되는 데이터의 양에 따라 비례하여 처리시간이 증가하는 알고리즘을 표현한다. 아래의 예는 Big O가 최악의 경우에 대한 성능을 보여주고 있다. for 루프 중간에 찾아져 일찍 수행이 끝날 수도 있다. 그러나 Big O 표기는 항상 최대로 반복이 이뤄질 경우를 상정한 한계값을 가정한다.
bool ContainsValue(String[] strings, String value)
{
for(int i = 0; i < strings.Length; i++)
{
if(strings[i] == value)
{
return true;
}
}
return false;
}
O(N²)
O(N²) 는 수행성능이 입력 데이터의 크기의 제곱승에 비례하여 증가하는 상황을 표현한다. 이는 일반적으로 중첩된 반복 수행문이 주어진 데이터 값들에 대해 수행할 경우 일반적으로 발생한다. 더 깊은 수준의 반복문은 O(N³), O(N⁴)의 결과로 나타난다.O(2ⁿ)
O(2ⁿ) 은 입력 데이터가 하나 증가할 때마다 처리시간이 두배씩 증가하는 경우를 표현한다. O(2ⁿ)이 수행시간은 아주 빠르게 증가하여 엄청나게 커진다.Log N
- 이진 탐색은 N개의 정렬된 원소가 들어 있는 배열에서 원소 x를 찾을 때 사용
- 처음에는 원소 N개가 드러있는 배열에서 시작한다. 한 단계가 지나면 탐색해야할 원소의 개수가 N/2로 줄어들고, 한 단계가 더 지나면 N/4로 줄어든다. 그러라가 원소를 찾거나 탐색해야 하는 원소가 하나만 남으면 탐색을 중지
- 총 수행 시간은 N을 절반씩 나누는 과정에서 몇단계 만에 1이 되는지에 따라 결정된다.
- 2⁴ = 16 --> log₂16 = 4
- log₂N = k ---> 2^K = N
- 원소의 개수가 절반씩 줄어든다면 그 문제의 수행시간은 O(logN)이 될 가능성이 크다.
- big-O에서 로그의 밑은 고려할 필요가 없다.
재귀적으로 수행 시간 구하기
int f(int n){
if(n <= 1){
return 1;
}
return f(n -1) + f(n -1);
}
- 함수 f가 2번 호출된 것을 보고 O(N^2)라고 생각하면 틀렸다.
- 수행시간을 추측하지 말고 코드를 하나씩 읽어나가면서 수행시간을 계산해보면 f(4)는 f(3)을 2번 호출한다. f(3)은 f(2)를 거쳐서 f(1)까지 호출한다.
- 트리의 깊이가 N이고 각 노드는 두개의 자식 노드를 가지고 있다. 따라서 깊이가 한 단계 깊어질 때마다 이전보다 두배 더 많이 호출하게 된다.
- 재귀 함수에서 수행시간은 보통 O(분기^깊이)로 표현된다. 여기서 분귀란 재귀함수가 자신을 재호출 하는 횟수를 뜻한다. 따라서 위의 경우에는 수행시간이 O(2^N)이 된다.
- 이 알고리즘의 공간 복잡도는 O(N)이 된다. 전체 노드의 개수는 O(2^N)이지만 특정 시간에 사용하는 공간의 크기는 O(N)이다. 따라서 필요한 가용 메모리의 크기는 O(N)이 된다.
0 개의 댓글:
댓글 쓰기