빠른 알고리즘 vs 느린 알고리즘
알고리즘의 속도는 어떻게 비교할까?
알고리즘의 속도는 시간으로 비교하지 않는다. 연산이 완료되기까지의 시간은 컴퓨터의 성능이 결정하기 때문이다. 알고리즘의 속도는 완료까지 걸리는 절차의 수 로 비교하게 된다.
시간복잡도!
시간복잡도란 알고리즘을 수행하는데 사용되는 연산들이 몇 번 이루어지는가에 대한 것을 상대적 지표로 나타낸 것이다.
연산에는 산술, 대입, 비교, 이동이 있다.
성능 측정에 사용되는 표기법은 Big-O, Big-Omega(Ω), Theta(θ) 크게 세 가지로 나뉜다.
Big-O : 최악의 경우를 고려
- 최악의 경우 n번까지 수행해야 한다.
Big-Omega(Ω) : 최고의 경우를 고려
- 최소 n번은 수행해야 한다.
Theta(θ) : 평균
- Big-O와 Big-Omega(Ω) 의 평균
대부분의 코딩 테스트 환경은 1초 ~ 10초 정도 시간 제한이 걸려 있다.
그렇기 때문에 내가 작성하고자하는 코드가 최악의 경우에 시간이 몇초가 걸릴지 체크를 해야하기 때문에 Big-O 표기법으로 바라봐야한다.
보통 10^7 횟수 보다 작아야 한다.
예를 들어 자료의 양이 10만개 정도라면 O(nlogn)이하의 시간 복잡도가 나오게끔 코드를 작성해야 한다. 그래야 연산하는데 1억번 보다 적게 나오기 때문이다.
시간복잡도 표기법 - O(1)
시간복잡도 표기법 - O(logn)
시간복잡도 표기법 - O(n)
시간복잡도 표기법 - O(nlogn)
시간복잡도 표기법 - O(n^2)
Better Than Yesterday