효율적인 알고리즘을 짜기 위해선 런타임과 메모리 사용을 최소화시키는 것이 중요하다. 그 중 런타임, 즉 시간 복잡도를 계산하는 법을 먼저 알아보겠다.
표기법
시간복잡도 표기 방식에는 아래와 같이 세가지가 있다.
- 최상의 경우: 오메가 표기법 (Big-Ω Notation)
- 최악의 경우: 빅오표기법 (Big-O Notation)
- 평균의 경우: 세타 표기법 (Big-θ Notation)
일반적으로 가장 많이 사용되는 것은 빅오 표기법이다. 빅오 표기법은 계수와 낮은 차수의 항을 제외시키는 방법이다. (예, 2n²-2n+2 > O(n^2)로 표기) 빅오 표기법이 개발자들에게 중요한 이유는, 최악의 경우를 대비해서 알고리즘을 짜야하기 때문이다. 빅오 표기법에 가장 큰 영향을 미치는 것은 input의 개수이다. Input N 하나 기준으로 몇번의 연산이 반복되는지 계산한 것이 빅오표기법이다.
Big-O Notation Cases
- O(1) – 상수 시간 : 입력값 n 이 주어졌을 때, 알고리즘이 문제를 해결하는데 오직 한 단계만 거칩니다.
- O(log n) – 로그 시간 : 입력값 n 이 주어졌을 때, 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듭니다.
- O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가집니다.
- O(n^2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱입니다.
- O(C^n) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱입니다.
BIG O NOTATION 알고리즘 예시
O(log n) | Binary search |
O(n) | Simple search |
O(n * log n) | Quicksort |
O(n2) | Selection sort |
O(n!) | Traveling salesperson |
BIG O Complexity 계산법
1. 상수를 제거한다.
void printAllItemsTwice(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
printf("%d\n", arr[i]);
}
for (int i = 0; i < size; i++)
{
printf("%d\n", arr[i]);
}
}
위와 같은 경우에는 array에 대해서 두번의 code execution이 진행되기 때문에 O(2n)이다. 상수를 제거해줘서 O(n)이 된다.
void printFirstItemThenFirstHalfThenSayHi100Times(int arr[], int size)
{
printf("First element of array = %d\n",arr[0]);
for (int i = 0; i < size/2; i++)
{
printf("%d\n", arr[i]);
}
for (int i = 0; i < 100; i++)
{
printf("Hi\n");
}
}
위와 같은 경우에는 time complexity는 O(1 + n/2 + 100)로 계산된다. 이 역시 상수를 제거해줘서 O(n)이 된다.
2. 가장 큰 차수의 항만 남긴다.
void printAllNumbersThenAllPairSums(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
printf("%d\n", arr[i]);
}
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
printf("%d\n", arr[i] + arr[j]);
}
}
}
위와 같은 경우에는 time complexity는 O(n + n^2)로 계산된다. N이 커질 수록 더 영향력이 큰 항, 즉 가장 큰 차수의 항만 남겨두고 삭제해준다. 따라서 위의 코드는 O(n^2)이다.
비슷한 논리로 다음과 같이 표현될 수 있다:
- O(n3 + 50n2 + 10000) -> O(n3)
- O((n + 30) * (n + 5)) -> O(n2)
'개발공부 > 개발' 카테고리의 다른 글
[Javascript] Object를 value 값으로 간단하게 정렬해보기 (0) | 2021.05.26 |
---|---|
[python] 'ord' method를 사용해서 character를 정수로 나타내는 방법 (0) | 2021.05.19 |
Tree Traversal - Pre-order, In-order, Post-order (0) | 2021.03.02 |
Breadth First Search (BFS) - 너비 우선 탐색 (0) | 2021.02.28 |
Request param, query, body의 차이점 (0) | 2020.10.31 |
효율적인 알고리즘을 짜기 위해선 런타임과 메모리 사용을 최소화시키는 것이 중요하다. 그 중 런타임, 즉 시간 복잡도를 계산하는 법을 먼저 알아보겠다.
표기법
시간복잡도 표기 방식에는 아래와 같이 세가지가 있다.
- 최상의 경우: 오메가 표기법 (Big-Ω Notation)
- 최악의 경우: 빅오표기법 (Big-O Notation)
- 평균의 경우: 세타 표기법 (Big-θ Notation)
일반적으로 가장 많이 사용되는 것은 빅오 표기법이다. 빅오 표기법은 계수와 낮은 차수의 항을 제외시키는 방법이다. (예, 2n²-2n+2 > O(n^2)로 표기) 빅오 표기법이 개발자들에게 중요한 이유는, 최악의 경우를 대비해서 알고리즘을 짜야하기 때문이다. 빅오 표기법에 가장 큰 영향을 미치는 것은 input의 개수이다. Input N 하나 기준으로 몇번의 연산이 반복되는지 계산한 것이 빅오표기법이다.
Big-O Notation Cases
- O(1) – 상수 시간 : 입력값 n 이 주어졌을 때, 알고리즘이 문제를 해결하는데 오직 한 단계만 거칩니다.
- O(log n) – 로그 시간 : 입력값 n 이 주어졌을 때, 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듭니다.
- O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가집니다.
- O(n^2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱입니다.
- O(C^n) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱입니다.
BIG O NOTATION 알고리즘 예시
O(log n) | Binary search |
O(n) | Simple search |
O(n * log n) | Quicksort |
O(n2) | Selection sort |
O(n!) | Traveling salesperson |
BIG O Complexity 계산법
1. 상수를 제거한다.
void printAllItemsTwice(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
printf("%d\n", arr[i]);
}
for (int i = 0; i < size; i++)
{
printf("%d\n", arr[i]);
}
}
위와 같은 경우에는 array에 대해서 두번의 code execution이 진행되기 때문에 O(2n)이다. 상수를 제거해줘서 O(n)이 된다.
void printFirstItemThenFirstHalfThenSayHi100Times(int arr[], int size)
{
printf("First element of array = %d\n",arr[0]);
for (int i = 0; i < size/2; i++)
{
printf("%d\n", arr[i]);
}
for (int i = 0; i < 100; i++)
{
printf("Hi\n");
}
}
위와 같은 경우에는 time complexity는 O(1 + n/2 + 100)로 계산된다. 이 역시 상수를 제거해줘서 O(n)이 된다.
2. 가장 큰 차수의 항만 남긴다.
void printAllNumbersThenAllPairSums(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
printf("%d\n", arr[i]);
}
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
printf("%d\n", arr[i] + arr[j]);
}
}
}
위와 같은 경우에는 time complexity는 O(n + n^2)로 계산된다. N이 커질 수록 더 영향력이 큰 항, 즉 가장 큰 차수의 항만 남겨두고 삭제해준다. 따라서 위의 코드는 O(n^2)이다.
비슷한 논리로 다음과 같이 표현될 수 있다:
- O(n3 + 50n2 + 10000) -> O(n3)
- O((n + 30) * (n + 5)) -> O(n2)
'개발공부 > 개발' 카테고리의 다른 글
[Javascript] Object를 value 값으로 간단하게 정렬해보기 (0) | 2021.05.26 |
---|---|
[python] 'ord' method를 사용해서 character를 정수로 나타내는 방법 (0) | 2021.05.19 |
Tree Traversal - Pre-order, In-order, Post-order (0) | 2021.03.02 |
Breadth First Search (BFS) - 너비 우선 탐색 (0) | 2021.02.28 |
Request param, query, body의 차이점 (0) | 2020.10.31 |