[알고리즘 + 자료구조 = 프로그램] 최선의 알고리즘을 찾는 기준
알고리즘이란?
알고리즘(Algorithm)
어떤 문제를 해결하기 위해 밟아 나가는 연속적 단계.
-
명확함(Definiteness): 각 단계가 명료하고 간결하며 모호하지 않음
-
효율성(Effectiveness): 각 동작이 문제 해결에 기여함
-
유한함(Finiteness): 알고리즘이 유한한 단계를 거친 후 종료됨
-
정확성(Correctness) : 입력이 같으면 항상 같은 결과를, 정확한 답을 제시.
몇가지 중요 예외도 있긴함.
정확성이 필요하지 않은 경우나 근삿값으로 충분한 경우.
최선의 알고리즘.
실행 시간은 알고리즘을 평가하는 기준 중 하나.
알고리즘이 무엇이 최선인지는, 필요한 단계가 얼마나 되는지 알아보는 걸로 알 수 있다.
이 때, 필요한 단계는 입력값인 n에 의해 좌우된다.
확인해야하는 게 많으면, 자연히 단계 수도 늘어난다.
이 때 해야하는 건 정확한 단계 수가 아니라,
데이터 크기에 따라 늘어나는 정도가 어느 정도 되는지 파악하는 게 중요하다.
빅 O 표기법(Big O notation).
n이 커짐에 따라 알고리즘의 시간 또는 공간의 요건이 얼마나 커지는지를 나타내는 수학적 표기법.
빅 O 표기법은 T(n)에서 규모 함수를 도출하는데, 규모(Order of Magnitude)란 차이가 아주 큰 등급 체계에서의 크기 차이를 뜻한다.
가장 크게 영향을 주는 수식만 확인하여 크기를 가늠하는 것이다.
가장 널리 사용되는 규모 함수를 최선에서 최악까지 나열하자면 이렇다.
! 시간 복잡도
상수 -> 로그 -> 선형 -> 선형 로그 -> 2차-> 3차 -> 지수
O(1) -> O(log(2)n)-> O(n) -> O(nlogn) -> O(n^2) -> O(n^3) -> O(2^n)
해시 테이블 -> 이진탐색 -> 순차탐색 -> 병합정렬, 퀵정렬, 힙정렬 -> 버블정렬, 삽입정렬 -> 행렬곱셈 -> ...
! 점근 표기법
대략적으로 나타냄.(자세하게의 반대말.)
- O(Big O) 표기법: 알고리즘 성능이 최악인 경우(수행 시간의 상한)를 나타낼 때 사용
- Ω(Big Omega) 표기법: 알고리즘의 성능이 최선인 경우(수행 시간의 하한)를 나타낼 때 사용
- Θ(Big Theta) 표기법: 알고리즘이 처리해야 하는 수행 시간의 상한과 하한을 동시에 나타냄
빅 O가 어떤 경우에도 보장되는 알고리즘 성능이라 주로 쓴다.
그런데 퀵은 최악일때 복잡도가 훨씬 커지지만, 그래도 선호하게 되는 이유가 뭘까?
힙 정렬은 약간 느려도 평균 속도가 보장되기는 한다.
그렇지만 안정성이 보장받지 못한다.
퀵정렬은 피봇만 잘 선택된다면 시간 복잡도가 준수하다. 평균 성능이 가장 좋다.
병합정렬은 피봇에 따라 복잡도가 갈리지 않는다. 최악의 경우 가장 좋다. 그러나 추가적인 메모리가 필요하다.
그래서 안정성이 보장되고, 추가적 메모리가 필요하지 않는 퀵 정렬을 쓰는 것이다.
