알고리듬 성능 평가
@ 3~5차시
💫 알고리듬의 성능 평가, F Evaluation
어떤 알고리듬이 더 좋냐에 대한 평가 기준은 실행 시간과 메모리 공간.
(동일한 목적을 가지고, 결과가 정확하다는 가정하에)
현대에 와서는 메모리가 넉넉해져서, 실행 시간을 좀 더 우선적으로 봄.
(물론 메모리가 한정적인 임베디드는 공간도 중요)
- 같은 문제, 다른 성능
- 다항식 계산 : 각 항 계산 < 호너의 규칙
- 1~n 정수 합 : for 계산 < 등차수열의 합 공식
- 정의역 밖 요소 탐색 : 순차탐색 < 정렬된 배열에서 순차탐색 (Invalid 값에서 Early Return) < 이진탐색
- 실행 시간 측정의 문제점
- 컴퓨터 스펙에 따라
- 언어, 컴파일러, 프로그래밍 스타일 및 코딩 표준에 따라
- 실행할 때마다 실행 시간이 달라질 수 있음
- 가능한 모든 입력에 대해, 정확한 결과(!근사)를 출력하도록
완성해야
실행 시간 측정은 알고리듬 자체의 성능 이외의, 외부 영향을 많이 받는다.
→ 복잡도 분석
어림잡아 3~5억 번의 연산/1초
어떤 연산을 하는지에 따라
단순한 연산 : 비트 AND, OR, 비교, 덧셈
복잡한 연산 : 곱셈, 나눗셈, 대입, 함수 호출
2000만?
보통 문제에서 1~5초 정도가 주어진다
-> 입력 범위를 보고 문제에서 요구하는 시간복잡도를 유추
💫 복잡도 분석
계산이나 추론 등을 통하여 알고리듬을 실행하는데 필요한 양을 결정하는 작업
(시간 복잡도, 공간 복잡도 = 실행 시간, 메모리 공간)
현실적으로, 측정 없이 불가능한데, 측정은 외부 영향을 많이 받음
현실적인 대안으로, 실행시간을 가늠할 수 있는 간접적 지표을 계산하여 시간 복잡도의 기준으로
시간 복잡도
입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계
- 시간 복잡도의 기준
- 연산 실행 횟수
- 연산 실행 회수는 n에 대한 함수 꼴 T(n) = 그래프
- 최댓값 찾기 : 탐색 대상 숫자의 수에 따라
- 행렬 곱 : 행렬의 행과 열의 값에 따라
- 정렬 : 정렬 대상 원소의 수에 따라
- 연산 실행 회수는 n에 대한 함수 꼴 T(n) = 그래프
- 명령문 실행 횟수
- 큰 알고리듬에서 연산 실행 횟수 계산 어려움
- 기준연산 실행 횟수
- 기준연산 : 실행 시간의 계산에 있어서 영향을 가장 많이 주는 연산
- 기준연산이 명확하지 않으면 어려움
- 연산 실행 횟수
N이하의 수 중에서 가장 큰 2의 거듭제곱수를 반환하는 함수 (N은 10억 이하의 자연수)
로그의 정의에 입각해서 k = LogN, O(LogN)
@ U 중간고사 출제 : 버블 정렬, 기준연산 기준 실행횟수를 구하시오. (n = 101, 등차등비)
점근 분석, Asymptotic Analysis
= 복잡도 함수를 ‘단순한’ 근사 함수(무한으로 가면 비슷한 꼴)로
→ 최고 차항을 계수를 1로 하여 추출
계수, 나머지 항 생략해도 되나?
→ 무한으로 갈수록, 식에서 최고 차항 비율은 겁나 커진다
→ 무한으로 갈수록, 계수 < 지수
복잡도 등급 - 입력 크기(n) 비례 복잡도(결과, 처리시간) 증가
→ 상수, 로그, 선형, 선형로그, n차, 지수, 팩토리얼, …
@ 정렬 - 선형로그
@ 제곱 - 행렬 합
@ 세제곱 - 행렬 곱
@ msps - 초당 백만번 연산
@ 단순 연산(비트 연산 등)과 상대적 복잡 연산과의 괴리
@ flops - 초당 부동소수점 연산
공간 복잡도 (Space Complexity)
입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계
512MB = 1.2억개의 int
기억하면 좋다
int 1개가 4바이트라는 걸로 기억
예를 들어 크기가 5억인 배열이 필요하다 -> 틀린 풀이니까 다른 풀이를 고민
💫 점근 표기법
@ U 중간고사 출제 : (두 가지 경우에 대해서만 n^2, 다른 모든 경우에 대해서는 n * log n 시간복잡도를 가지는 알고리듬에 대해) Big O, Big Θ, 최악의 경우 의미
-> ‘최악의 경우’가 붙으면 세타가 더 적절하다 O도 틀린 건 아니지만..
-> 최악의 경우 세타와 그냥O는 같은 뜻인가? X
Big O, Big Θ, Big Ω
@ 소문자와 구별되기에, Big 붙여야
🫧 Big O, 점근적 상한
아무리 많아도 이정도 걸린다
I.E.
→ T(n) = 2x + 4 일때, O(3x)
→ 5n^2 + 3n - 10 = O(n^3)
→ 5n^2 + 3n - 10 = O(n^2)
→ 5n^2 + 3n - 10 != O(n)
When
→ 입력 데이터에 따라 증가율이 달라지는 경우
→ 정확한 복잡도는 모르고, 상한은 아는 경우
→ 관례적 (그냥 많이 써서)
상한의 불확실성 (빡빡한 상한, 느슨한 상한)
→ 정의를 만족하는 가장 낮은 차수를 사용하는 것이 원칙
@ =은 equal, is가 아니라 포함되어 있다 라는 의미
🫧 Big Ω, 점근적 하한
최소한 이정도 걸린다
I.E.
→ T(n) = 2x + 4 일때, Ω(n)
When
→ 입력 데이터에 따라 증가율이 달라지는 경우
→ 정확한 복잡도는 모르고, 하한은 아는 경우
→ 다른 점근 표기법 보완 (보통 혼자 쓰지 않음)
f(n) = O(g(n)) <=> g(n) = Ω(f(n))
🫧 Big Θ, 점근적 상한과 하한이 일치
대략 이정도다
I.E.
→ T(n) = 2x + 4 일때, Θ(n)
When
→ 정학한 복잡도 함수를 아는 경우
🫧 BlaBla
복잡도 - O, Ω
(~한 경우) 복잡도 - Θ
동일한 기능의 알고리즘 비교
A = O(n^2), B = O(n^3)
A가 B보다 빠르다 X
A가 B보다 점근적으로 빠르다 O
n의 값이 고려되어야 한다
I.E. A = 10^5 * n^2, B = n^3, n < 10^5 라면 A < B
n이 작으면 시간 차이 별로 없거나, 오히려 점근 복잡도가 낮은 알고리즘이 더 느릴 수 있다
점근 복잡도는 수학과 공학의 절묘한 균형을 요구
@ TODO: 공학 ?
점근 복잡도 쉽게 구하기
- n에 따라, 순차적인 명령문(블록)은 점근 복잡도 함수를 더한다
- n에 따라, 중첩된 명령문(블록)은 점근 복잡도 함수를 곱한다
- 부프로그램(함수)도 점근 복잡도를 반영
최악, 최선, 평균 복잡도
n 같더라도 집합-순서에 따라 실행 시간 달라지는 알고리즘
Big O 점근석 상한 만을 나타내기도
최선 <= 평균 <= 최악 복잡도
최악과 최선 복잡도가 같다면, 평균적인 경우도 같고, 이는 Θ 표기법으로
평균 복잡도
최악에 가까운, 버블 정렬, 삽입 정렬
최선에 가까운, 퀵 정렬
의미 차이
최악의 경우 Θ(n^2)
→ 최악의 경우 n^2가 걸린다
최악의 경우 O(n^2)
→ 최악의 경우, 정확하게는 모르겠지만 그 상한이 n^2이다
최악의 경우, 최선의 경우, 평균적인 경우 Θ(~)
== O(~), Ω(~)
💫 Big O Notation
코테에서는 빅오 표기법만 보면 된다.
알고리즘이 얼마나 빠른지 표시하는 특별한 방법
주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법.
i.e. n개의 원소, 단순 탐색은 n번 연산, O(n)
초 같은 시간 단위는 어디로? 빅오 표기법은 속도를 시간 단위로 세지 않음
연산 횟수를 비교하기 위한 것
🫧 주의 : 알고리듬간 속도 비교 시
100개의 원소, 단순 100번, 이진 7번
이진 탐색은 단순 탐색보다 15배 빠른 알고리듬이다? XXX
10억개의 원소, 단순 10억번, 이친 32번
이 경우에는 이진 탐색이 단순 탐색보다 3천3백만배 빠르다
리스트의 크기에 따라 실행 시간이 증가하는 비율이 다르다
-> 알고리듬의 실행시간이 얼마나 걸리는지만 고려할 것이 아니라
-> 리스트의 크기가 증가할 때 어떻게 증가하는지를 파악할 필요가 있다
🫧 주의 : Big O는 최악의 경우에 대한 것
i.e. 단순 탐색, 사전에서 a를 한 번에 찾았으므로 O(1)? XXX
빅오는 최악의 경우에 대한 것
절대로 ~보다는 느려지지 않는다는 사실에 대한 보장
🫧 빅 오 실행시간의 예
- O(1) : 상수 시간
- 5, 16, 36
- O(LogN) 로그 시간 Logarithmic Time
- 이진탐색
- O(N) 선형 시간 Linear Time (데이터 크기와 실행 횟수가 똑같은)
- 5N + 3, 2N + 10LogN, 10N
- 단순탐색
- O(NLogN) 다항 시간
- NLogN + 30N + 10, 5NLogN + 6
- 퀵 정렬 같이 빠른 정렬 알고리듬
- O(N2) 다항 시간
- N2 + 2N + 4, 6N2 + 20N + 10LogN
- 선택 정렬과 같이 느린 정렬 알고리듬
- O(2N) 지수 시간
- O(N!)
- 12!은 약 5억
- 외판원(세일즈맨) 문제와 같이 정말 느린 알고리듬
- Traveling Salesperson Problem
- 모든 도시는 가장 짧은 거리의(시간의) 경로
- 아직 이것보다 빠른 알고리듬이 알려지지 않음
- 대략적인 답을 얻는 것 밖에 (이진 탐색 트리)
| N의 크기 | 허용 시간 복잡도 |
| N <= 11 | O(N!) |
| N <= 25 | O(2n) |
| N <= 100 | O(N4) |
| N <= 500 | O(N3) |
| N <= 3,000 | O(N2LogN) |
| N <= 5,000 | O(N2) |
| N <= 1,000,000 | O(NLogN) |
| N <= 10,000,000 | O(N) |
| 그 이상 | O(LogN), O(1) |
절대적인 기준은 아니다 (느낌만)
🫧 로그
log10100이라는 수는 “10을몇 번 곱해야 100이 될까?” 하고 묻고 있는 것
10 * 10 = 100 이니까 답은 2
그러니까 log10100 = 2
즉, 로그는 거듭제곱의 반대말
빅오 표기법에서 모든 log 함수는 log2를 뜻한다
🫧 요약
- 알고리듬의 속도는 시간이 아니라 연산 횟수가 어떻게 증가하는지로 측정
- 입력 데이터의 크기가 늘어날 때 알고리듬의 실행속도가 얼마나 증가하는지 알 수 있다
- 알고리듬의 실행시간은 빅 오 표기법
- O(log n)은 O(n)보다 빠르고, 찾으려는 리스트의 원소의 개수가 증가하면 상대적으로 더 빨라진다.