- 알고리즘이란?
문제를 해결하는 유한한 수의 단계적 절차로서 입력에 대해 컴퓨터에서 수행 가능한 연산을 통해 수행 결과인 해(또는 답)를 출력한다.
- 알고리즘의 속성
정확성(correct) : 알고리즘은 주어진 입력에 대해 올바른 해를 주어야
수행성(excutable) : 알고리즘의 각 단계는 컴퓨터에서 수행이 가능하여야
유한성(finite) : 알고리즘은 유한 시간 내에 종료되어야
- 알고리즘의 성능 분석
시간 복잡도(Time Complexity) - 수행 시간
공간 복잡도(Space Complexity) - 알고리즘이 수행되는 동안 사용되는 메모리 공간의 크기
대부분의 경우 시간 복잡도 사용 : 대부분의 알고리즘들이 비슷한 크기의 메모리 공간을 사용하기 때문
- 알고리즘의 분석 종류
최악 경우 분석(Worst-case Analysis) - '어떤 입력에 대해서도 알고리즘의 수행 시간이 얼마 이상은 넘지 않는다' 라는 상한
평균 경우 분석(Average-case Analysis) - 입력의 확률 분포를 가정, 균등 분포(Uniform Distribution) = 입력이 랜덤하게 주어진다는 가정
최선 경우 분석(Best-case Analysis) - 가장 빠른 수행 시간을 분석, 최적(optimal) 알고리즘을 찾는 데 활용
- 점근적 표기법
수행 시간 - 기본 연산 횟수를 입력 크기에 대한 함수로 표현
함수 - 여러 개의 항을 가지는 다항식으로 표현
점근적 표기법(Asymptotic Notation) 사용
최악 경우 : Big-O 표기 사용
- Big-O 표기
모든 n ≥ n₀ 에 대해서 f(n) ≤ cg(n)이 성립하는 양의 상수 c와 n₀이 존재하면, f(n) = O(g(n))이다.
- O-표기법 찾기
다항식에서 최고 차수 항만을 취한 뒤, 그 항의 계수 제거하여 g(n)을 정한다.
ex) 2n² + 3n³ = O(n³) / 5n² + 4n = O(n²)