시간 복잡도(Time Complexity )
Big-O 표기법 : 시간 복잡도를 나타내는 방법
❗️효율적인 알고리즘 고민
- 알고리즘 문제를 풀다 보면 문제에 대한 해답을 찾는 것이 가장 중요하다.
- 그러나 그에 못지않게, 효율적인 방법으로 문제를 해결을 했는지도 중요하다.
- 혹시 문제를 풀다가 ‘이것보다 더 효율적인 방법은 없을까?
또는 이게 제일 좋은 방법이 맞나?’라는 생각을 해 본 적이 있는가?- 효율적인 방법을 고민한다는 것은 시간 복잡도를 고민한다는 것과 같은 말이다.
❗️시간복잡도
- 문제를 해결하기 위한 알고리즘의 로직을 코드로 구현할 때, 시간 복잡도를 고려한다는 것은 무슨 의미일까?
- 알고리즘의 로직을 코드로 구현할 때, 시간 복잡도를 고려한다는 것은
‘입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?’라는 말이다.- 효율적인 알고리즘을 구현한다는 것은 바꾸어 말해 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성했다는 이야기이다.
그리고 이 시간 복잡도는 주로 빅-오 표기법을 사용해 나타낸다.
👉 가장 자주 사용되는 표기법은?
빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문이다.
“최소한 특정 시간 이상이 걸린다” 혹은 “이 정도 시간이 걸린다”를 고려하는 것보다 “이 정도 시간까지 걸릴 수 있다”를 고려해야 그에 맞는 대응이 가능하다.
👉 Big-O 표기법의 종류
O(1), O(n), O(log n), O(n2), O(2n)
-
O(1) : 일정한 복잡도(constant complexity)라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다. 다시 말해 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다는 의미이다.
- 파이썬의 경우 index, 인덱싱, length, append, pop, clear
-
O(n) : 선형 복잡도(linear complexity)라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.
- 비교, 삽입, 삭제, 복사 등
-
O(log n): 로그 복잡도(logarithmic complexity)라고 부르며, Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가진다.
- BST(Binary Search Tree)가 이에 해당
- BST에선 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어든다.
-
O(n2) : 2차 복잡도(quadratic complexity)라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.
-
O(2n) : 기하급수적 복잡도(exponential complexity)라고 부르며, Big-O 표기법 중 가장 느린 시간 복잡도를 가진다.
- 재귀로 구현하는 피보나치 수열은 O(2n)의 시간 복잡도를 가진 대표적인 알고리즘이다.
