[알고리즘] 3. 점근적 표기법과 성능 분석
1. 점근적 표기법
1) 점근적 분석 (Asymptotic Analysis)
• 입력 크기가 충분히 큰 경우를 분석하는 방법
• 작은 입력에서는 차이가 미미하지만, 입력 크기가 커질수록 비효율적인 알고리즘은 심각한 성능 저하를 초래
• 입력 크기 nn이 무한대로 커질 때 알고리즘의 복잡도를 간단하게 표현하는 표기법 사용
• 서로 다른 알고리즘을 객관적으로 비교할 수 있는 기준 제공
2) 알고리즘의 성능 분석 방법
실제 실행시간 측정
• 프로그램을 실제로 구현하여 실행 시간을 측정
• 동일한 하드웨어 환경에서 비교 필요
복잡도 분석
• 직접 구현하지 않고 연산 횟수를 기반으로 수행 시간을 예측
• 연산 횟수는 일반적으로 입력 크기 nn의 함수로 표현됨
• 시간 복잡도: 수행 시간과 관련
• 공간 복잡도: 필요한 메모리 공간과 관련
3) 계산 복잡도 표기법
• 알고리즘의 수행 시간을 분석할 때 시간 복잡도를 사용
• 입력 크기 nn이 증가할수록 가장 큰 차수를 가진 항의 영향이 절대적
4) 점근적 표기법 (Asymptotic Notation)
빅-오 (Big-O)
• 최악의 경우 수행 시간의 상한을 나타냄
• 아무리 오래 걸려도 이 시간 안에는 끝난다는 의미
빅-오메가 (Big-Omega)
• 최상의 경우 수행 시간의 하한을 나타냄
• 최소한 이만큼의 시간이 걸린다는 의미
빅-세타 (Big-Theta)
• 수행 시간의 상한과 하한을 동시에 나타냄
• 알고리즘의 수행 시간이 특정 범위 안에 있음을 보장
2. 알고리즘의 복잡도
1) 알고리즘 분석
• 알고리즘이 사용하는 자원(시간, 메모리 등)의 양을 평가
• 실행 시간을 기준으로 성능 분석 수행
2) 바람직한 알고리즘
• 명확하고 이해하기 쉬워야 함
• 불필요한 기호적 표현을 최소화하여 가독성을 높여야 함
• 같은 문제를 해결하는 여러 알고리즘 중 더 효율적인 것을 선택
3) 알고리즘의 복잡도
• 시간 복잡도: 알고리즘이 실행되는 데 걸리는 시간
• 공간 복잡도: 알고리즘이 사용하는 메모리 공간
• 일반적으로 알고리즘 비교 시 시간 복잡도를 중심으로 평가
3. 점화식 (Recurrence Relation)
1) 점화식이란?
• 어떤 함수를 이전의 작은 값들과의 관계로 정의하는 방식
• 재귀 함수의 복잡도를 분석할 때 유용
2) 점화식 예시
• 예: an=an−1+2a_n = a_{n-1} + 2
• 예: f(n)=f(n−1)+f(n−2)f(n) = f(n-1) + f(n-2) (피보나치 수열)
• 예: f(n)=f(n/2)+nf(n) = f(n/2) + n
3) 피보나치 수열을 활용한 점화식
• 토끼 한 쌍이 2달 후부터 새끼를 낳는다고 가정
• 각 달마다 토끼의 쌍 수를 점화식으로 표현
• 점화식: F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)
• 초깃값: F(0)=1,F(1)=1F(0) = 1, F(1) = 1
이 내용은 휴넷사회복지평생교육원의 알고리즘 강의를 듣고 정리한 것입니다.