시간 복잡도
시간 복잡도 (Time Complexity)는 프로그램의 입력값와 연산 수행 시간의 상관관계를 나타내는 척도를 말한다.
수치가 낮으면 낮을수록 더 효율적인 알고리즘을 뜻한다.
일반적으로 알고리즘에서 효율성을 따질때는 프로그램이 돌아가는 하나하나의 단계를 따지는 게 아닌, 시간 복잡도를 사용하게 된다. 하나하나 단계별로 효율성을 결정하기는 매우 어렵기 때문이다.
시간 복잡도는 크게 3가지 표기법으로 나타낼 수 있다.
- Big-O - 최악의 경우 (해당 알고리즘은 Big-O보다 더 오래 걸릴 수 없다)
- Big-Ω - 최선의 경우 (해당 알고리즘은 Big-Omega보다 더 빠를 수 없다)
- Big-θ - 평균의 경우 (Big-O + Big-Omega를 합쳐 표현한 것과 같음)
이 중에서 최악의 상황을 나타내는 Big-O notation 이 가장 빈번하게 사용된다.
애초에 최악을 고려해서 효율성을 따지는 것이라 항상 worst case scenario에 대응할 수 있기 때문이다.
Big-O 표기법
예를 들자면 어떤 게임이 오픈을 했는데 최악의 상황을 고려하지 않고 1000명 정도 오겠지 하는 생각으로 딱 그 정도의
인풋 정도로 무난하게 돌아가는 알고리즘을 구현하였다. 하지만 광고를 너무 잘 한 나머지, 100,000명의 유저가 한 번에 들어오려 했는데, 이렇게 되면 서버는 바로 다운될 것이고 유저의 불만 글은 폭증할 것은 당연하다.
이처럼 대부분 모든 경우에서 (현실에서도) 항상 최악의 상황을 고려하는 자세를 갖는다면 어떤 상황에서도 유연한 대처가 가능하다.
위에서 설명했듯이, Big-O는 프로그램상의 알고리즘 효율을 따질 때 가장 자주 사용되며, 최악의 상황인 경우를 따지기 때문에 최악의 상황이 발생하더라도 대처할 수 있게 된다.
그럼 각각의 함수가 뭘 의미하는지 알아보자.
O(1)
Constant Complexity
인풋 데이터와 관련 없이 항상 일정한 실행 시간을 갖는다.
가장 빠른 시간 복잡도
O(n)
Linear Complexity
인풋 데이터의 크기와 실행 시간이 정비례 한다. (사이즈가 크면 실행시간도 길어짐)
1중 for 반복문
O(log n)
Logarithmic Runtime Complexity
인풋 데이터의 사이즈가 커질수록 실행 시간도 log 만큼 짧아짐
연산의 단계들이 연산마다 특정 요인에 의해 줄어듬
Binary Search Tree ( 경우의 수가 단계별로 절반씩 줄어든다)
O(n^2)
Quadratic Runtime Complexity or Polynominal
input값이 증가할때마다 실행 시간이 n의 제곱에 비례함 O(n^2), O(n^3), O(n^4)... 같은 O(n^2)로 취급
2중 ~ 다중 for 반복문,
삽입 정렬 (Insert Sort), 버블 정렬(Bubble Sort), 선택 정렬(Selection Sort)
O(2^n)
Exponential Complexity
가장 느린 시간 복잡도
input데이터의 크기에 따라 실행 시간은 2의 n제곱만큼 비례
보통 모든 조합과 방법을 시도할 때 사용
재귀를 이용한 피보나치, 하노이의 탑 문제 등
적절한 시간 복잡도
후에 코딩테스트를 풀게 되면 지금 연습할 때처럼 시간이 넉넉하게 주어지지 않고 제한 시간 내에 제한된 자원으로 정확하게 프로그램을 만들어야 한다. 따라서 시간제한과 주어진 데이터의 크기 제한에 따른 시간 복잡도를 예상해 보는 게 좋다.
| 데이터 크기에 따른 적절한 시간 복잡도 | |
| 데이터 크기 | 시간 복잡도 |
| N < 500 | O(N^3) |
| N < 10,000 | O(n^2) |
| N < 10,000,000 | O(N) |
아래의 cheat sheet를 보면 한눈에 적절한 시간 복잡도를 알 수 있다.
'programming > ALGORITHM' 카테고리의 다른 글
| Brute-Force Algorithm (0) | 2022.06.06 |
|---|---|
| [TBC] Search Algorithm (0) | 2022.06.06 |
| Greedy Algorithm (0) | 2022.05.31 |