상수 함수
f(n) = c
- 이 때 c = 5, c = 27, c = 2¹⁰과 같이 고정된 임의의 상수임
- 즉, 어떠한 매개변수 n에 대해 상수 함수 f(n)은 c를 반환함
- 다시 말해 n의 값에 상관없이 f(n)은 항상 상수 c와 같다.
- 상수 함수는 간단한 만큼 알고리즘 분석에 유용하다.
- 왜나면 두 숫자 더하기, 값을 변수에 넣기, 두 개 숫자 비교하기 같은 기본 연산에서 스탭의 수를 특정 지으므로.
로그 함수
- 자료 구조와 알고리즘의 분석에서 놀라운 것은 로그 함수가 흔하게 사용된다는 것.
- f(n) = logₐn 이고, a > 1)이 흔하게 사용 됨
- 특히, logₐn과 같거나 큰 정수 중 가장 작은 정수를 쉽게 계산할 수 있다.
- 그 이유는 그 숫자가 1보다 작거나 같을 때까지 n을 a로 나눌 수 있는 횟수와 동일하기 때문
예를 들면,
27 / 3 / 3 / 3 = 1 이므로 log₃27의 값은 3이다.
64 / 4 / 4 / 4 = 1이므로 log₄64의 값은 3이다.
- 컴퓨터가 정수를 2진으로 저장하기 때문에 로그 함수를 위해 자주 사용되는 기저는 2임
- 2인 기저는 너무 흔해서 일반적으로 2일 때 기저를 생략
일차함수
f(n) = n
- 주어진 입력값 n에 대해 함수 f는 n을 반환함
- n개의 원소가 각각에 대해 기본 연산을 해야 하는 경우임
예를 들면 숫자 x와 크기 n의 배열의 각 원소와의 비교는 n번의 비교를 요구함
일차 함수는 컴퓨터 메모리에 없었던 n개 객체를 처리하는데 최고의 실행시간을 나타냄
n log n 함수
f(n) = n log n
- 입력 값 n에 대해 기저 2의 n 로그 값에 n을 곱한 값을 반환함
- 일차 함수보다 약간 빠르게 증가하고 이차 함수보다 꽤 느림
이차 함수
f(n) = n²
- 입력 값 n이 주어지면 f는 n의 자신의 곱을 반환함
- 알고리즘 분석에서 2차 함수가 나타나는 주된 이유는 중첩 반복문을 사용하기 때문
알고리즘의 분석
- 자료구조란 자료를 구성하고 접근하는 체계적인 방법
- 알고리즘은 유한한 시간 내에 어떤 일을 수행하는 단계적인 절차
- 이러한 개념은 컴퓨팅의 중심에 있고 자료구조와 알고리즘이 양질로 평가될 수 있는지
- 정확한 분석도구가 있어야 한다.
실험적 연구
- 알고리즘이 구현됐을 때 다양한 테스트 입력을 통해 프로그램을 실행하고 걸린 시간을 측정해서 비교 및 연구
- 이러한 테스트는 특정 입력 크기에 대한 특정 실행 시간이 나오지만,
- 일반적으로 입력 크기에 의해 좌우되는 일반적인 실행 시간이 필요함
- 그러면 다양한 표본값을 가지고 실험을 하면 될까?
- 그러나 여기도 문제가 있다.
- 실험은 제한된 테스트 입력에 의해서만 이루어짐
- 동일한 하드웨어와 소프트웨어 환경에서 실험이 수행되지 않는다면 표본이 의미가 없음
따라서 앞으로 알고리즘을 입력크기 n을 갖는 함수로써 각각 알고리즘에 대하여
실행 시간 특징을 기술하는 함수 f(n)과 연관시키는 것이 목적임
기본 연산
- 변수에 값 배정
- 함수 호출
- 산술연산 수행
- 두 수의 비교
- 배열 인덱싱
- 객체 참조 따라감
- 함수로부터 반환
기본 연산은 실행시간으로 상수값을 갖는다.
그래서 실행 시간을 결정하려는 시도 대신 얼마나 많이 수행됐는지를 따짐
점근적 표기
- 알고리즘에서 '큰 그림' 접근법으로 입력 크기 n의 함수로써 실행 시간 증가율에 초점을 맞춰보자
- arrayMax와 같은 알고리즘 실행시간이 n에 비례해서 증가함
- (실행 시간은 특정 컴퓨터에 따른 상수인자와 n의 곱과 같음)
int arrayMax(int* arr, int size)
{
int currMax = arr[0];
for (int i = 0; i < size - 1; i++)
{
if (currMax < arr[i])
currMax = arr[i];
}
return currMax;
}
빅 오 표기법
- 어떤 문제에 대해 매개변수 n을 이용하여 실행 시간이나 메모리 사용량을 특정하는데 널리 사용됨
- 예를 들어 arrayMax 알고리즘에서 가장 큰 원소를 찾는데 관심이 있다면 배열 원소의 수를 n으로 정하는 것
- 빅오 표기법을 사용하여 알고리즘 arrayMax의 실행 시간에 대해
- 어떠한 하드웨어나 소프트웨어 환경에서도 수학적으로 정확한 명제를 기술할 수 있다.
예제 - n개의 정수를 갖는 배열에서 최대 크기의 원소를 갖는 알고리즘 arrayMax는 O(n) 시간 안에 실행된다.
증명 - 알고리즘 arrayMax의 각 반복에서 실행되는 기본 연산의 개수는 상수임
따라서 각 기본 연산이 상수 시간동안 실행됨
그러므로 입력 크기 n에 대한 알고리즘 arrayMax의 실행 시간은 최대 상수 시간 n이다.
그러므로 알고리즘 arrayMax의 실행 시간은 O(n)이라고 결론지을 수 있다.
빅 오 표기법의 특성
- 빅 오 표기법은 함수 증가에 영향을 미치는 주요 구성요소에만 초점을 맞추고,
- 낮은 차수와 상수 인자는 무시될 수 있도록 허용함
ex) 5n⁴ + 3n³ + 2n² + 4n + 1은 O(n⁴)이다.
그래서 다항식의 최고자 항은 그 다항식의 점근적 증가율을 결정하는 항이다.
가장 간단한 항들로 함수 특징 기술하기
- 함수의 특징을 기술할 때에는 가능한 원래 함수에 근접한 빅 오 표기법을 사용해야 한다.
- f(n) = 4n³ + 3n² 를 O(n⁵)로 표기해도 틀린 건 아니지만 O(n³)이 더 정확하다.
- 빅오 표기법을 사용할 경우에 진실을 얻도록 힘써야 한다.
빅 오 표기법에 있어서 더 낮은 차수의 항들을 포함시키는 것은 좋지 않다.
빅 오 표기법을 사용할 때에는 해당 함수를 가장 단순한 항들로 기술하여야 함.
댓글