국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한
박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다
Algorithm Analysis
알고리즘 : 어떤 문제(Problem)를 해결하기 위한 절차나 방법을 공식화한 형태로 표현한 것
=> 여기서 문제란 입력(Input)과 출력(Output)의 관계
정렬 문제를 예시로 봤을 때
Input : 정렬되지 않은 숫자들의 목록
Output : 오름차순으로 정렬된 숫자들의 목록
한 문제는 다양한 알고리즘으로 해결할 수 있음
Problem : n을 n번 더한 값은?
누가봐도 3번을 채택할텐데
가장 효율적이고 쓰기 좋은 알고리즘을 선택해야하고 이것은 곧 효율성과 용이성이 좋다는 의미
(알고리즘에서는 효율성을 주로 신경씀)
그럼 알고리즘의 효율성은 어떻게 측정할까?
효율적인 알고리즘이란 한정된 자원으로 문제를 해결하는 것임
=> 자원(Resource)에는 시간, 공간 등이 있음
(여기서 공간은 메모리 공간을 의미)
효율성 측정 방법에는 실제로 돌려보고 측정하는 실험적(Empirical) 방법과 기본 연산 수를 세는 이론적(Theoretical) 방법이 있음
실험적 방법
- time() 을 이용해 알고리즘 시작 전, 후 시간의 차를 이용하여 시간을 측정
- 실행 중간마다 memory_info()를 호출하여 메모리 공간을 측정
- 직관적이라는 장점이 있음
- 기기, OS, 언어, 구현방법 등 환경에 따라 가변적이라는 단점이 있음
- 입력 크기에 따른 성능의 경향성 파악이 어려움 (다양한 입력 크기에 대해 실험을 해야 성능의 변화를 체계적으로 분석 가능)
=> 입력 크기별로 전부 실행해봐야 알 수 있음
이론적 방법
복잡도 분석(Complexity Analysis)
- 시간 복잡도 (Time Complexity) : 기본 연산의 수
(n개의 입력일 때 기본 연산을 n 만큼 사용하는지 n^2 만큼 사용하는지를 나타냄) - 공간 복잡도 (Space Complexity) : 메모리 사용량
(사용하는 변수의 양이라고 생각하면 됨)
기본 연산이란?
사칙연산 (+, -, *, /) , 대입연산 (=), 비교연산(<, <=, ..) 등등
대개, 복잡도는 입력 데이터의 크기 n에 의해 결정됨
- T(n) : 입력 n에 대한 시간 복잡도 함수
- S(n) : 입력 n에 대한 공간 복잡도 함수
Best, Worst and Average Cases
입력 크기가 같아도 입력에 따라 복잡도가 다를 수 있음!
=> 경우를 나눠서 분석하자
- Best case : 가장 적은 자원을 사용하는 경우
- Average case : 평균적으로 자원을 사용하는 경우
(일반적인 경우의 성능) - Worst case : 가장 많은 자원을 사용하는 경우
(성능 보장에 활용 : 어떤 경우라도 이보다는 좋음)
Best case를 고려할 일이 있을까..?
입력을 best case에 비슷하게 맞출 경우 best case가 중요할 수 있음!
예시
Best case : T(n) = 1
=> q가 nums의 가장 앞에 있는 경우
Worst case : T(n) = n
=> q가 nums의 가장 마지막에 있거나, 아예 없는 경우
Average case : T(n) = (n+1)/2
=> 값이 존재한다고 가정했을 때 모든 가능한 경우의 기댓값
Average case를 구할 때 각 위치에서 q가 발견될 확률은 1/n 이고
- 첫 번째 위치에서 발견되면 1번 비교
- 두 번째 위치에서 발견되면 2번 비교
- …
- 마지막 위치에서 발견되면 n번 비교
이므로 시그마 1~n 까지 계산하면 n(n+1) / 2 여서 해당 식이 나옴!
Asymptotic Analysis
Introduction to Asymptotic Analysis
알고리즘을 분석하려면 항상 기본 연산 수를 일일이 세야 할까?
정확한 연산 수를 세는 것 보다 입력 크기에 따라 연산 수가 변하는 경향을 파악하는 것이 중요함
=> 대략적으로 세는 것이 보편적 (점근적 분석법을 사용하자)
점근적 분석(Asymptotic Analysis)
입력 크기가 아주 클 때의 복잡도 분석이다
=> 무한대로 근접한다고 생각하면 분석이 간단해짐!
(n이 무한대로 근접함에 따라 함수가 변화하는 양상을 살펴보자는 뜻)
왜 입력 크기가 클 때를 분석할까?
입력 크기가 작을 땐 어차피 복잡도가 낮음 (전부 빨리 실행됨)
또한 우세항(Dominant Factor) 만 찾으면 되기 때문에 분석이 단순해짐
=> 상수 계수(Constant Coefficient) 도 무시 가능
정말 입력 n이 커짐에 따라 상수 계수를 무시할 수 있을까?
Algorithm A : T(n) = 2^n
Algorithm B : T(n) = n^10
라고 할 때
n이 커지면 결국 Algorithm B가 빠르다는 것을 알 수 있음
Algorithm B 의 T(n)에 상수 1000을 붙여 T(n) = 1000 x n^10 으로 만든다고 하더라도
n이 커지면 결국 Algorithm B가 빠르다는 것을 알 수 있음
=> 상수는 무시할 수 있다!
복잡도 함수의 서열은 어떻게 될까?
Big-O, Big-Omega, Big-Theta
점근적 표기법(Asymptotic Notations)는 우리가 앞서 다뤘던 점근적 분석(우세항만 보고, 상수 계수는 무시하고 ...)을 수학적으로 명확하게 정의하기 위한 표기법이다!
- Big-O Notation
=> n이 아주 클 때 c · f(n) 보다 값이 작은 함수의 집합을 의미함
=> f(n)이 상한 (upper bound)
T(n)이 O(f(n)) 에 속하는지 증명하려면?
T(n) <= c · f(n) for all n >= n0 를 만족하는 c와 n0을 찾으면 됨!
=> T(n)은 입력값이 아무리 증가하더라도 상한인 f(n)과 비슷한 양상으로 증가하는 형태를 띠게 됨
T(n) = 4n - 4 ∈ O(n), O(n^2), O(n^3) ... 임
=> 가장 tight한 bound를 찾는 것이 중요함!
성능 평가에 중요한 영향을 미치지 않는 계수, 상수항 굳이 신경 쓰지 X
2n + 1 ∈ O(1/2n)
O(n) = O(2n) = O(n +2)
- Big-Omega Notation
=> n이 아주 클 때 c · f(n) 보다 값이 큰 함수의 집합
=> f(n)이 하한 (lower bound)
T(n)이 Ω(f(n)) 에 속하는지 증명하려면?
T(n) >= c · f(n) for all n >= n0 를 만족하는 c와 n0을 찾으면 됨!
=> T(n)은 입력값이 아무리 증가하더라도 하한인 f(n)과 비슷한 양상으로 증가하는 형태를 띠게 됨
- Big-Theta Notation
=> 상한과 하한이 모두 f(n)인 함수 집합
T(n)이 Θ(f(n))에 속하는지 증명하려면?
T(n)이 O(f(n)) 과 Ω(f(n)) 모두에 속하는지 증명하면 됨!
Simplifying Rules
'Algorithm' 카테고리의 다른 글
| L05 - Heapsort (2) | 2024.10.06 |
|---|---|
| L04 - Merge Sort & Quicksort (2) | 2024.09.27 |
| L03 - Basic Sorting Algorithms (1) | 2024.09.25 |
| L02 - Recurrences (1) | 2024.09.17 |
| 시간복잡도와 디버깅 (3) | 2024.01.17 |
