[Python Algorithm] Ch2. 알고리즘 효율성 분석
2.1 효율성 분석의 기초
알고리즘 효율성
- 시간 효울성: 가장 중요한 요소. 결과를 빨리 도출하는 알고리즘
- 공간 효율성: 컴퓨터 메모리를 더 적게 사용하는 알고리즘이 좋은 알고리즘
알고리즘의 복잡도를 분석하기 위해 확인해야 하는 사항들
- 입력의 크기
- 핵심적인 기본 연산
- 입력 크기 증가에 따른 처리시간의 증가
- 입력의 특성이 알고리즘 효율성에 미치는 영향
입력의 크기
정렬 문제에서 입력의 크기는 항목의 개수
- 찾으려는 값 자체의 크기는 상관이 없음
- 리스트에서 값을 찾는 경우 리스트의 길이가 입력의 개수
- 행렬의 경우 입력의 개수가 여러개(가로, 세로의 길이)
기본 연산
알고리즘 안에서 가장 중요한 연산(ex. 다중 주프의 가장 안쪽에 있는 연산)을 찾아 실행되는 횟수 계산
- 예: n의 거듭제곱을 구하는 3가지 알고리즘 => 처리시간이 다 다름
- 첫 번째 방법: n * n
- 두 번쨰 방법: n을 n번 더함
- 세 번쨰 방법: 1을 n * n번 더함
+, -, /, * 간의 연산 속도 차이는 고려하지 않음
복잡도 함수와 증가 속도
시간 복잡도 함수(T(n)): 연산의 수를 입력의 개수 n의 함수로 나타낸 것
- 입력 크기가 충분히 큰 범위에 대해서만 관심이 있음
- 시간 복잡도 함수의 각 항의 계수는 영향을 주지 않음
- n의 증가에 따른 증가속도에만 관심이 있음
- 예: 위의 예시
- 첫 번째 방법: T(n) = 2
- 두 번째 방법: T(n) = 2n
- 세 번째 방법: T(n) = 2n^2 => 입력의 크기가 커지면 시간복잡도가 제곱으로 커짐
입력의 특성과 알고리즘 효율성
세 가지 일고리즘의 효율성
- 최선의 경우: 실행시간이 가장 적은 경우
- 평균적인 경우
- 최악의 경우: 입력의 구성이 알고리즘의 실행시간을 가장 많이 요구하는 경우
=> ‘최악의 경우’에 대한 성능이 가장 중요
2.2 점근적 성능 분석 방법
점근적 표기
임이의 크기 n이 무한대로 커질 때의 복잡도를 간단하 표현하기 위해 사용
- 복잡도 함수를 최고차항만을 계수 없이 취해 단순화
빅오 표기법
어떤 함수의 점근적 상한
- 3n^2 + 4n => O(n^2)
알고리즘의 점근적 성능 클래스들
O(1), O(logn), O(n), O(nlogn), O(n^2), O(n^3), O(2^n), O(n!)
빅오메가 표기법
어떤 함수의 점근적 하한
- 3n^3 + 4n => Omega(n^2)
빅세타 표기법
어떤 함수의 점근적 상한임과 동시에 점근적 하한