All
1. 알고리즘 분석
정확성 분석
•
유효한 입력에 대해 일정 시간내에 정확한 결과의 생성 여부
효율성 분석
•
알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정/평가
•
공간 복잡도 (space complexity): 메모리의 양 = 정적 공간 + 동적 공간
•
시간 복잡도: 수행시간 = 알고리즘의 실행에서부터 완료까지 걸리는 시간
시간복잡도
알고리즘 수행시간 = Σ{각 연산이 수행되는 횟수}
수행 시간에 영향을 미치는 요인
입력크기 (리스트 원소의 개수, 행렬의 크기 등)
•
입력크기 n이 커질수록 수행시간 증가 > 입력크기 n의 함수 f(n)으로 표현
입력 데이터의 상태
•
S(n) : 크기 n인 입력들의 집합
•
P(i) : 입력 i가 발생할 확률
•
T(i) : 입력 i 에 대한 알고리즘의 수행시간
•
평균 수행시간
•
최선 수행시간
•
최악 수행시간 > "아무리 오래 걸려도 이 시간안에는 수행된다" 알고리즘 간 우열을 가리기 좋음
2. 점근 성능
점근성능이란
•
입력 크기 n이 무한히 커짐에 따라 결정되는 성능
•
수행시간의 정확한 값이 아닌 어림값으로 수행시간의 증가 추세 파악이 쉬움
•
수행시간의 다항식 함수에서 최고차항만을 계수 없이 취해서 표현
점근성능의 표기법
빅오(Big-O)
•
최악 수행 시간의 상한을 나타냄.
•
입력 크기 n이 증가할 때, 수행 시간이 "최대" 얼마나 걸릴 수 있는지를 분석.
•
어떤 입력에서도 이보다 느리진 않다는 보장을 함.
•
최대 f(n)만큼 시간이 걸린다
빅오메가(Big-Ω)
•
최선(Best-case) 수행 시간의 하한을 나타냄.
•
어떤 입력에서 최소한 이만큼의 시간이 걸린다.
•
최소 f(n)의 시간이 걸린다
빅쎄타(Big-Θ)
•
시간 복잡도의 상한과 하한이 일치하는 경우.
•
수행 시간이 항상 f(n)과 비슷하게 걸린다는 의미.
•
최악과 최선이 f(n)으로 수렴한다
시간 복잡도 순서
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(2n) < O(n!)
표기법 | 이름 | 예시 | 특징 |
O(1) | 상수 시간 | 해시 테이블 조회, 배열 인덱싱 | 입력 크기와 관계없이 항상 일정한 시간 |
O(log n) | 로그 시간 | 이진 탐색 | 입력 크기가 커져도 상대적으로 증가 속도가 느림 |
O(n) | 선형 시간 | 단순 반복문 (배열 순회) | 입력 크기에 비례하여 실행 시간 증가 |
O(n log n) | 선형로그 시간 | 퀵 정렬, 병합 정렬 | 거의 모든 효율적인 정렬 알고리즘 |
O(n²) | 이차 시간 | 버블 정렬, 선택 정렬, 삽입 정렬 | 중첩된 반복문 (이중 for문) |
O(2ⁿ) | 지수 시간 | 피보나치 (재귀), 부분집합 생성 | 입력 크기가 조금만 커져도 매우 느려짐 |
O(n!) | 팩토리얼 시간 | 외판원 문제(완전 탐색) | 가장 비효율적, 거의 사용 불가능 |
빅오 함수에 따른 연산 시간의 증가추세
n | logn | nlogn | n² | n³ | 2ⁿ |
1 | 0 | 0 | 1 | 1 | 2 |
2 | 1 | 2 | 4 | 8 | 4 |
4 | 2 | 8 | 16 | 64 | 16 |
8 | 3 | 24 | 64 | 512 | 256 |
16 | 4 | 64 | 256 | 4096 | 65536 |
32 | 5 | 160 | 1024 | 32768 | 4294967296 |
3. 순환 알고리즘(재귀)
•
알고리즘의 수행 과정에서 자기 자신의 알고리즘을 다시 호출하여 수행하는 형태의 알고리즘
•
재귀적인 알고리즘에서는 현재 문제를 더 작은 문제로 나누어 해결하는데 이 과정에서 수행시간을 점화식으로 표현할 수 있음
점화식
•
이전 단계의 값을 이용해 다음 값을 계산하는 형태의 수식
•
예를 들어 이진탐색은 문제를 절반으로 줄여서 풀기 때문에 수행시간은 다음과 같음
•
T(n/2) : 문제를 반으로 줄여서 해결할때의 수행 시간
•
O(1) : 현재 단계에서 수행하는 추가 작업의 시간
•
즉 현재 크기 n의 문제를 크기 n/2로 줄이고 그 과정에서 추가적인 일정한 작업(이진 탐색에서는 가운데 원소 비교와 방향 결정 과정)을 수행
점화식의 폐쇄형
•
위와 같은 점화식은 재귀적인 형태라 실제 계산이 어려움. 이를 일반적인 수식으로 변환한 것이 폐쇄형 표현
•
반복적인 관계를 없애고 한번에 계산할 수 있도록 만든 것
위의 이진 탐색의 점화식을 폐쇄형으로 풀면
1. 첫번째 호출:
2. 두번째 호출:
3. 세번째 호출:
이렇게 반복하다 보면
점화식은 입력 크기가 1이 될 때 끝나므로, 이 되는 k를 찾으면
양변에 로그를 취하면,
처음 점화식에서 은 이 되고, k는 이 되므로
따라서 최종적으로 이렇게 식이 나오게 된다.
실제 알고리즘들의 점화식과 폐쇄형 정리
알고리즘 | 점화식 | 폐쇄형 |
이진 탐색 | T(n) = T(n/2) + O(1) | O(log n) |
퀵 정렬 (최악) | T(n) = T(n-1) + O(n) | O(n²) |
퀵 정렬 (최선, 평균) | T(n) = 2T(n/2) + O(n) | O(n log n) |
병합 정렬 | T(n) = 2T(n/2) + O(n) | O(n log n) |