안녕하세요 Gliver 입니다.
이번 글에서는 시간 복잡도에 대해 알아보겠습니다.
목차
- 시간 복잡도의 의미
- 자주 쓰이는 시간 복잡도
- 실제 문제에서 시간 복잡도
시간 복잡도의 의미
시간 복잡도는 프로그램이 돌아가는 데 걸리는 시간을 표기한 것입니다.
프로그램의 기본 연산의 횟수는 상수와 변수로 표현 가능합니다.
따라서, 시간 복잡도를 표현할 때 사용하는 문자도 상수와 변수뿐입니다.
ex) "3n + 1000" 번의 기본 연산이 이루어지면, 변수 n과 상수 1000으로 시간 복잡도를 나타낼 수 있음.
자주 쓰이는 시간 복잡도
저희는 Big-O 표기법에 대해서만 다룰 것입니다.
Big-O 표기법은 프로그램 동작 시간에 가장 큰 영향을 주는 값을 중심으로 시간복잡도를 표기합니다.
큰 영향을 주는 값이라는 것은 시간 복잡도 식에서 변수를 모두 ∞로 보냈을 때, 가장 큰 영향을 미치는 문자를 남기는 것입니다.
예를 들어, "2n² + 100n + 11" 번의 기본 연산이 이루어지면
f(n) = 2n² + 100n + 11이라 하고 n→∞을 수행하면
f(n)에 가장 큰 영향을 미치는 문자는 2n²입니다.
따라서, Big-O 표기법으로 표기하면 앞의 계수는 버리고 O(n²)으로 나타냅니다.
이해를 돕기 위해 아래에 예시를 적어 놓겠습니다.
(시간 복잡도에 있는 식은 실제 연산 횟수를 의미)
| Example | 시간 복잡도 (실제 연산 횟수) | Big-O 표기 |
| ex1 | f(n, m, k) = 3n² + 2m + 4k + 10000 | O(n²+m+k) |
| ex2 | f(n) = 10000 | O(1) |
| ex3 | f(n, m) = 3n² + 2log m + 1000 | O(n² + log m) |
이러한 표기법의 문제점은 f(n) = 10000n, g(n) = n이라는 두 식이 있을 때
실제 연산 횟수가 꽤 차이가 있음에도 표기법이 O(n)으로 같다는 점 등이 있습니다.
따라서, Big-O 표기법은 프로그램이 돌아가는 데 걸리는 정확한 시간이 아닌 대략적인 시간을 표시한다고 생각하시면 될 거 같습니다.
자주 쓰이는 시간 복잡도는 아래와 같이 표로 적어 놓겠습니다.
문제에서 시간 복잡도에 가장 큰 영향을 주는 변수를 n이라고 가정
| 시간 복잡도 | 간단한 설명 | 쓰임새 |
| O(1) | - 수행 시간이 입력의 크기에 영향을 받지 않음. | - 수학 관련 문제 |
| O(log n) | - 이러한 코드는 단계마다 입력의 크기를 반으로 줄여 나감. | - 이분 탐색 |
| O(n) | - 선형 시간으로, 입력의 크기만큼 수행한다. - 대부분 문제의 경우, 입력을 최소한 1번은 살펴봐야 하기 때문에 O(n) 시간 복잡도는 굉장히 효율적이라고 할 수 있다. |
- 선형 탐색 - (대부분의 문제에서) 가장 효율적인 시간 복잡도 |
| O(n log n) | - 이 시간 복잡도는 O(n) x O(log n) 또는 O(log n) x O(n)으로 해석할 수 있다. - O(n) x O(log n)은 n번을 탐색하면서 각각의 탐색에서 log n번의 처리를 해주는 경우이다. - O(log n) x O(n)은 log n번을 탐색하면서 각각의 탐색에서 n번의 처리를 해주는 경우이다. |
- 병합 정렬 - 이분 탐색 (응용) |
| O(n^k) k는 2이상 |
- 보통 for문의 중첩이 k인 경우에 해당한다. - 상황에 따라서 재귀함수도 이와 같은 시간 복잡도를 가진다. |
- 조합 (∵ nCk는 n^k의 시간 복잡도) |
실제 문제에서 시간 복잡도
실제 문제에선 시간 복잡도를 어떻게 써야 할까요?
문제로 예를 들어 보겠습니다.
[문제]
배열의 크기가 n인 배열이 정렬된 상태로 주어지고, 특정한 값이 배열에 존재하는지를 물어봅니다.
이 문제의 시간 제한은 1초라고 합시다. (1 ≤ n ≤ 10억)
컴퓨터는 1초에 1억 번 연산을 할 수 있다고 생각하면 됨.
"그냥 하나씩 살펴보면서 그 값이 있는지 없는지 찾아보면 되겠네" 라는 생각으로 선형 탐색을 하시면
시간 복잡도는 O(n)이고, 최악의 경우엔(n이 10억이면) 약 10억 번의 연산이 이루어지므로
시간은 약 10초가 걸리므로 시간제한을 충족하지 못합니다.
따라서, 저희는 정렬된 상태에서 사용할 수 있는 이분 탐색 알고리즘을 사용하여 O(log n)라는 시간 복잡도로 문제를 해결할 수 있습니다.
최악의 경우(n이 10억인 경우)에도, (log 1000000000 ≒ ) 30번의 연산만에 문제를 해결할 수 있음.
(시간 복잡도에서 log의 밑을 생략하면 보통 밑이 2인 log를 의미)
이렇게 시간 복잡도를 알면 내가 짠 풀이가 문제의 시간 제한을 충족하는지 충족하지 못하는지를 코드를 짜기 전에 판별할 수 있습니다.
궁금한 점이나 코멘트는 댓글로 남겨주세요!
- 알고리즘 공부법 : https://gliver.tistory.com/6
- 알고리즘 목차 : https://gliver.tistory.com/7
'✏️ 알고리즘 > 기본 알고리즘' 카테고리의 다른 글
| [06강] 순열 알고리즘 (0) | 2022.01.16 |
|---|---|
| [05강] 조합 알고리즘 (2) | 2022.01.10 |
| [04강] 유클리드 알고리즘 (0) | 2022.01.07 |
| [03강] 에라토스테네스의 체 알고리즘 (0) | 2022.01.07 |
| [02강] 나머지(모듈러, modulo) 연산 (0) | 2022.01.02 |