[알고리즘] 시간 복잡도 쉽게 이해하기

▶시간 복잡도, 이정도는 알고 있어야 한다!

---

 알고리즘을 공부할 때 가장 먼저 나오는 개념이 시간 복잡도입니다. 문제 해결에 있어서 시간 복잡도를 줄이는 방법을 이해하고 활용하는 것이 알고리즘을 배우는 주된 목적이기 때문이죠.

 시간 복잡도를 표기할 때 가장 일반적으로 사용되는 것은 빅오(O)-표기법 입니다. 어떤 알고리즘으로 문제를 해결하기 전에 입력 값에 따라 무엇을 어떤 변수로 놓을지 결정하고 난 뒤, 문제를 해결하는데 필요한 연산의 횟수를 식으로 구합니다. 구해진 식에서 최고 차항만을 남깁니다. 그 식에 최악의 입력 크기 값을 대입해보고 그 때에도 충분히 빠른 시간 내에 해결이 가능한지를 판단합니다. 

예를들어 1부터 N까지의 누적합을 구하는 문제가 있다고 합시다. N의 범위는 1<= N <= 1,000,000,000 입니다. 

반복문을 활용해 i를 1부터 N까지 증가시키며 그 값을 모두 더하는 알고리즘 A로 답을 구한다고 하면, O(N)이라는 식이 나옵니다. 문제에서 제한 시간이 1초라고 하면 알고리즘 A로는 제한 시간 내에 문제를 해결할 수 없습니다. 최악의 경우 N은 10억이 될텐데, 채점 서버에서 10억 번의 연산을 1초만에 할 수 없기 때문이죠. 그런데 1부터 N까지의 합을 구하는 공식을 외우고 있는 사람이라면 N*(N+1)/2을 계산하는 연산 한 번으로 문제를 해결할 수 있으므로 O(1)라는 식이 나옵니다. 입력 값에 따라서 연산의 수가 달라지지 않고 상수 시간만에 문제를 해결할 수 있는 경우엔 O(1)로 표기합니다.

 자신이 생각한 알고리즘이 충분히 빠른지 판단할 때, 1초에 1억번의 연산을 수행할 수 있다고 생각하고 계산하면 부족함이 없습니다.

[시간 복잡도 작은 순으로 나열]

O(1) < O(N) < O(logN) < O(N*logN) < O(N^2) < O(2^N) < O(N!)