1. 시간복잡도(Time Complexity)란?
시간복잡도란 간단히 말하자면, 어떠한 알고리즘의 연산 횟수를 수치로 나타낸 것을 말한다.
예를 들어, 어떤 자연수를 n번 더하는 문제를 풀기 위하여 세 가지의 알고리즘을 만들었다고 가정하자.
이처럼 입력의 개수 n에 따라서 변하는 연산의 수행횟수를 n에 대한 함수로 나타낸 것을 시간복잡도 함수라고 말하며, T(n)으로 표기한다.
시간복잡도 표기법은 크게 3가지가 있다.
- Ο(빅오 표기법) - 함수의 상한 (최악의 경우)
- Ω(빅오메가 표기법) - 함수의 하한 (최선의 경우)
- θ (빅세타 표기법) - 함수의 상한과 하한 (평균)
빅오 표기법 (Big-O notation)
빅오 표기법은, 간단히 말해 시간 복잡도의 점근적 상한을 나타낸 것이다. (즉 최악의 상황이어도 이것보단 좋다고 이해하면 되겠다.)
빅오 표기법 (Big-O notation)
함수 f(n)과 g(n)이 있을 때, 모든 n > n0에 대하여 |f(n)| ≤ c|g(n)| 을 만족하는 상수 c와 n0이 존재하면
f(n) = O(g(n))이다.
즉, g(n)에 상수 c를 곱한, c(g(n))의 그래프가,
n0 이상일때 f(n)보다 항상 크다면, f(n) = O(g(n))이다.
c와 n0은 어떤 값이든 상관이 없다.
n > n0일때 c|g(n)| 이 f(n) 이상이기만 하면 된다.
Example)
- f(n) = 2n+1일때, 빅오 표기법으로 나타내면 O(n)이다.
c = 3, n0 = 2일때 n > 2에 대하여 2n+1 ≤ 3n을 만족하기 때문이다.
- f(n) = 2n²-8n+3일때, 빅오 표기법으로 나타내면 O(n²)이다.
c = 5일때 f(n)과 5n² 의 그래프를 비교해보면 1보다 큰 모든 n에 대하여 f(n) ≤ 5n²을 만족하기 때문이다. (c=5, n0=1)
위의 두 예시를 통해서 눈치챘을 수도 있겠지만, 빅오 표기법은 사실 간단하게 구할 수 있는 방법이 있다.
만약 함수가 다항식으로 표현되었을 경우, 다항식의 최고차항이 곧 빅오 표기법이 된다. (최고차항의 계수는 생략)
-> 단, 모든 알고리즘의 복잡도가 다항식으로 표현되지는 않는다. logn, nlogn, 2ⁿ, n! 등 표현방법은 다양하다.
logn도 차수를 가지고 있기 때문에 함수식에 logn이 같이 들어있다면, 다항식의 빅오를 구할때처럼 그냥 없애버려서는 안된다.
앞서 말했듯이, 빅오 표기법은 상한을 표기한 것인데, 상한은 여러개가 존재할 수 있다. (예를 들어 f(n) = 2n+1일 때 O(n)도 될 수 있지만, O(n²), O(n³) 등등 도 가능하다.) 상한 중 가능한 낮은 차수로 표현하는 것이 보다 정확한데, 빅오 표기법에서는 상한이 여러개가 존재할 수 있으므로 약간의 문제점이 있다. 이 문제점을 보완하기 위해서 빅오메가, 빅세타 표기법이 만들어졌는데, 어떤 표기법인지 아래에서 더 알아보자.
빅오메가 표기법 (Big-Ω notation)
빅오 표기법과 반대되는 개념이다. 간단히 말해, 시간 복잡도의 점근적 하한을 나타낸 것이다. (즉, 최선일 때를 나타냈다고 이해하면 된다.)
빅오메가 표기법 (Big-Ω notation)
함수 f(n)과 g(n)이 있을 때, 모든 n > n0에 대하여 |f(n)| ≥ c|g(n)| 을 만족하는 상수 c와 n0이 존재하면
f(n) = Ω(g(n))이다.
빅세타 표기법 (Big- θ notation)
상한과 하한을 동시에 표시할 수 있는 표기법이다.
빅세타 표기법 (Big-θ notation)
함수 f(n)과 g(n)이 있을 때, 모든 n > n0에 대하여 c1|g(n)| ≤ |f(n)| ≤ c2|g(n)| 을 만족하는 상수 c1, c2와 n0이 존재하면 f(n) = θ(g(n))이다.
단 빅세타 표기법은 동일한 함수 g(n)으로 상한과 하한을 만들 수 있는 경우에만 적용할 수 있다.
(예를 들면, f(n) = 2n + 1 일때, n > 1에 대하여 n ≤ 2n + 1 ≤ 3n 이므로 f(n) = θ(n) 이다.)
'자료구조' 카테고리의 다른 글
| [자료구조] - 덱(deque)의 구조와 원형 덱 구현 (1) | 2024.01.05 |
|---|---|
| [자료구조] - 원형큐의 구조와 구현 (1) | 2023.12.10 |
| [자료구조] - 큐(queue)의 구조, 선형큐 구현하기 (0) | 2023.12.09 |
| [자료구조] - 스택(Stack)의 구조와 구현 (2) | 2023.12.03 |
