효율적인 알고리즘 고민
알고리즘 문제를 풀다 보면 문제에 대한 해답을 찾는 것이 가장 중요하다. 그러나 그에 못지않게, 효율적인 방법으로 문제를 해결을 했는지도 중요하다.
혹시 문제를 풀다가 ‘이것보다 더 효율적인 방법은 없을까?
또는 이게 제일 좋은 방법이 맞나?’라는 생각을 해 본 적이 있는가?
효율적인 방법을 고민한다는 것은 시간 복잡도를 고민한다는 것과 같은 말이다.**
알고리즘 복잡도(Complexity) 표현 방식
알고리즘의 복잡도를 표현하는 방식에는 크게 두 가지가 있다. 바로 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)이다.
시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다. 쉽게 말해 알고리즘의 실행 속도(성능)을 계산하는 표현 방법이다. 공간 복잡도는 알고리즘에서 사용하는 메모리 크기를 말한다.
알고리즘 시간 복잡도에 영향을 주는 주요 요소는 반복문이다. 반복되는 횟수가 많아질수록, 여러 반복문이 중첩될수록 시간 복잡도는 올라가게 된다.
알고리즘 성능 표기법
알고리즘 성능을 표기하는 방법은 크게 세 가지가 있다. 이 중 Big-O(빅 오) 표기법을 가장 많이 쓴다.
1) Big-O(빅 오) 표기법: O(n)
알고리즘 최악의 실행 시간을 표기한다. 가장 많이 그리고 가장 일반적으로 사용하는 표기법이다. 아무리 최악의 상황이라도 최소 이정도의 성능은 보장한다는 의미이기 때문에 Big-O 표기법을 가장 많이 쓴다.
2) Big-Ω(빅 오메가) 표기법: Ω(n)
오메가 표기법은 알고리즘 최상의 실행 시간을 표기한다.
3) Big-θ(빅 세타) 표기법: θ(n)
세타 표기법은 알고리즘 평균 실행 시간을 표기한다.
❗️O(1)
O(1)
O(1)는 일정한 복잡도(constant complexity)라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다.
❗️O(n)
O(n)
O(n)은 선형 복잡도(linear complexity)라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.
예를 들어 입력값이 1일 때 1초의 시간이 걸리고, 입력값을 100배로 증가시켰을 때 1초의 100배인 100초가 걸리는 알고리즘을 구현했다면, 그 알고리즘은 O(n)의 시간 복잡도를 가진다고 할 수 있다.
❗️O(log n)
O(log n)
O(log n)은 로그 복잡도(logarithmic complexity)라고 부르며, Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가진다.
자료구조에서 배웠던 BST(Binary Search Tree)를 기억하는가?
BST에선 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어든다.
