알고리즘의 자원(resource) 사용량 분석
자원이란 실행시간, 메모리, 저장장치, 통신 등
실행시간 분석
시간복잡도 (time complexity)
•
실행시간은 실행환경에 따라 달라진다
◦
HW, OS, 언어, 컴파일러 등
•
실행시간을 측정하는 대신 연산의 실행 횟수를 카운트 한다
•
연산의 실행횟수 → 입력 데이터의 크기에 관한 함수로 표현
•
데이터의 크기가 같더라도, 실제 데이터에 따라서 달라진다
◦
최악의 경우 시간복잡도 (worst-case analysis)
◦
평균 시간복잡도 (average-case analysis)
점근적(Asymptotic) 분석
•
빅오 표기법 사용
예시) - 상수 시간복잡도
int sample (int data[], int n)
{
int k = n / 2;
return data[k];
}
C
복사
→ n에 관계없이 상수 시간이 소요된다.
→ 시간복잡도는 O(1)
예시2) - 선형 시간복잡도
int sum (int data[], int n)
{
int sum = 0;
for (int i = 0; i < n; i++)
sum += data[i]; // <- 이 알고리즘에서 가장 자주 실행되는 문장, 실행 횟수 항상 n번
return sum;
}
C
복사
→ 모든 문장의 실행 횟수의 합은 n에 선형적으로 비례하며,
→ 모든 연산들의 실행횟수의 합도 역시 n에 선형적으로 비례한다
→ 선형 시간복잡도를 가진다고 말하고 O(n)
예시3) - 선형 시간복잡도 : 순차탐색
int search (int n, int data[], int target) {
for (int i = 0; i < n; i++) {
if (data[i] == target) // <- 가장 자주 실행, 실행횟수는 최악의 경우 n번
return i;
}
return -1;
}
C
복사
→ 최악의 경우 시간복잡도 O(n)
Quadratic
bool is_distinct (int n, int x[]) {
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if (x[i] == x[j]) // <- 가장 자주 실행, 최악의 경우 n(n-1)/2 번
return false;
return true;
}
C
복사
→ 최악의 경우 배열에 저장된 모든 원소 쌍을 비교하므로,
→ 비교 연산의 횟수는 n(n-1) / 2 이다
→ 최악의 경우 시간복잡도는