3. 함수의 증가
입력이 충분히 커지면 정확한 수행시간의 상수계수와 저차항은 입력 크기에 묻혀 버린다.
❓성장률
rate of growth
입렵값의 크기에 따라 함수가 얼마나 빨리 커지는지
즉, 실행시간의 성장률을 알고싶은 것!
우리가 알고 싶은건, 입력값 크기에 따른 알고리즘의 실행시간에 대한 예측이다.
프로그램을 쉽게 예측할수 있도록 불필요한 부분은 과감히 버리고 가장 중요한 부분만 추려서 함수로 간소화해야 한다.
예를 들어 0.6n²+1000n+3000 에서 n이 커질 수록 n²은 기하 급수적으로 커지게 된다.
❓접근적표기법
asymptotic notaion
상수 계수와 중요하지 않은 항목을 제거하는 표기법으로 big- 표기법, big-O 표기법, and big- 표기법이 있다.
❓big-
입력값 n이 커지면 실행시간은 k₂f(n)과 k₁f(n) 사이에 있게 된다.최고차항의 극히 일부분만으로도 저차항을 압도해 버리기 때문에 직관적으로 무시할 수 있다.마찬가지로 최고차항의 계수도 무시될 수 있는데, 최고차항의 계수와 저차항의 계수를 맞추어 바꿔주면 되기 때문이다.
세타 표기법을 사용하는 것은 실행 시간에 대해 점근적으로 근접한 한계값이 있다고 표현하는 것이다.입력값 n에 대해 점근적으로 커지고 위, 아래로 상수값 내에서 실행시간을 좁힐 수 있어 '근접한 한계값'으로 표현한 것.
❓big-O 표기법
점근적 상한선 k₂f(n)
실행시간은 최대 이만큼 커지지만 더 천천히 커질 수도 있다.
알고리즘의 최악의 경우 수행시간을 구할 때 사용한다.
❓ big-Omega) 표기법
점근적 하한선 k₁f(n)
적어도 이정도 수행시간이 걸린다.
❓o(g(n))
리틀 오 표기법
g(n)보다 엄격하게 느리게 증가하는 함수
f(n) = Ω(g(n)), f는 g보다 느리게 증가한다.
❓𝜔(g(n))
리틀 오메가 표기법
g(n)보다 엄격하게 빠르게 성장하는 함수
f(n) = Ω(g(n)), f는 g보다 빠르게 증가한다
엄격하게 더 느리게 성장하며, 동시에 g(n)와 위와 아래에서 제한되지 않는다.
입력값이 커질수록 1에 가깝게 알고리즘을 설계할수록 런타임에러가 발생하지 않을 것이다.
1. 사친연산, if문, 링크드리스트에서 삭제
2. 반복문에서 입력 값 일부 버림(소수), 이진검색
3. 선형, 링크드리스트에서 검색, 배열내 최대값 원소
4. 비선형, 분할 정복, 병합정렬
5. 2중 반복문, 삽입정렬, 선택정렬
7. 지수승, 모든 부분집합 검색, 브루노 포스
8. 모든 순열검색
3.1-1
3.1-2
3.1-3
빅오는 최악의 경우의 실행시간 즉, 상한값을 의미하므로 적어도라는 표현은 무의미 하다.
3.1-4
'알고리즘 > CLRS' 카테고리의 다른 글
| 2.3 알고리즘의 설계 (0) | 2023.08.23 |
|---|---|
| 2.2 알고리즘 분석 (0) | 2023.08.10 |
| 2.1 삽입 정렬 (0) | 2023.08.07 |
| 1.2 기술로서의 알고리즘 (0) | 2023.07.27 |
| 1.1 알고리즘 (0) | 2023.07.20 |
