수업 출처) 숙명여자대학교 소프트웨어학부 수업 "자료구조", 유석종 교수님
1. 성능 분석 (실행 가능한 기준)
- 공간 복잡도 (space complexity) : 필요한 메모리 양
- 시간 복잡도 (time complexity) : 프로그램 수행 시간
2. 공간 복잡도
- Fixed space requirements (Sc)
- 실행 도중에 변하지 않는 것
- 명령어, 단순 변수, 고정된 구조체 변수, 상수 등
- 공간 복잡도에 고려하지 않는다.
- Variable space requirement (Sv)
- 프로그램 실행 중에 요구되는 공간으로 가변적이고 예측이 어렵다.
- 함수 간 배열 전달, 재귀 호출 등
- 위험 요소를 내포하고 있으며, 공간 복잡도 평가에서 더욱 중요하다.
- S = (Sc +) Sv
- (ex1)
float abc (float a, float b, float c)
{
return a + b + b * c + (a + b - c) / (a + b) + 4.00;
}
-input과 output이 단순 변수로만 이루어져 있고, 명령어도 단순 계산이기 때문에 고정 메모리 공간만 활용하는 코드이다.
-Sv(abc) = 0
- (ex2)
float Sum (float list[], int n)
{
int i;
float total = 0;
for (i = 0l i < n; i++)
total = total + list[i];
return total;
}
- 함수를 호출할 때 배열이 전달되었기 때문에 가변 메모리 공간도 활용한다.
- 이 경우 시간 복잡도는 배열 전달 방법에 따라 결정된다.
- (ex3)
float rsum(float list[], int n)
{
if (n)
return rsum(list, n-1) + list[n-1];
else
return 0;
}
- 배열이 전달되었고, 재귀 호출이 사용되었기 때문에 가변 메모리 공간을 사용한다.
- 이 때 rsum함수가 처음을 제외하고 n번 호출되었다.
- 한 번 호출될 때마다 float list[], int n, rsum(list, n-1) 이 세가지 환경 변수들 (매개 변수 저장공간, 함수 회귀 주소) 이 저장되며, 각각 4bytes의 크기를 갖고 있기 때문에 S = 12n 이다.
- Call by value
- 함수에 배열 "값"을 직접 전달하는 방식이다.
- 배열 크기에 비례하는 추가적인 메모리 공간이 요구된다.
- Sv(sum) = n // n == array size
- (ex) Pascal
- Call by reference
- 함수에 배열 "주소"를 전달하는 방식이다.
- 추가적인 메모리 공간이 필요하지 않다.
- Sv(sum) = 0
- (ex) C
3. 시간 복잡도
- Time complexity (T)
- 알고리즘을 수행하는데 필요한 시간이다.
- 컴파일 시간(Tc)과 실행 시간(Te)으로 구성되는데, 컴파일은 완료되고 나면 더이상 수행되지 않으므로 실행 시간을 더 중요시한다.
- 실행 시간은 컴퓨터 하드웨어 환경에 따라 다르다.
- 따라서 실제 수행 시간보다는 명령문의 수를 시간 복잡도로 간주하여 사용한다.
- 실행 명령문 표
- 한 문장에 포함된 명령문의 수 (steps) 를 결정한다.
- 이 문장이 반복 실행되는 빈도 (frequency) 를 결정한다.
- (명령문 수) x (빈도)로 이 문장의 총 실행 횟수를 계산한다.
- 이 때 함수 헤더, 변수 선언, 블록의 시작과 끝은 명령문으로 간주하지 않는다.
- Σ steps * frequency
- iterative sum
float sum (float list[], int n) { // 1
int i; // 2
float temp = 0; // 3
for (i = 0; i < n; i++) // 4
temp += list[i]; // 5
return temp; // 6
} // 7
Statement | steps | frequency | total steps |
// 1 함수 헤더 | 0 | 0 | 0 |
// 2 변수 선언 | 0 | 0 | 0 |
// 3 변수 선언 후 "대입" | 1 | 1 | 1 |
// 4 반복문 & 변수 대입 [0, n] → n + 1 번 실행 | 1 | n + 1 | n + 1 |
// 5 계산문 [0, n-1] → i = n 이면 실행되지 않음, n 번 실행 | 1 | n | n |
// 6 return | 1 | 1 | 1 |
// 7 블록의 끝 | 0 | 0 | 0 |
total step counts | 2n + 3 |
- recursive sum
float rsum (float list[], int n) { // 1
if(n) // 2
return rsum(lsit, n-1) + list[n-1]; // 3
return 0; // 4
} // 5
Statement | steps | frequency | total steps |
// 1 함수 헤더 | 0 | 0 | 0 |
// 2 if 문 [0, n] → n + 1 | 1 | n + 1 | n + 1 |
// 3 함수 실행문 [0, n-1] → n | 1 | n | n |
// 4 return | 1 | 1 | 1 |
// 5 블록 끝 | 0 | 0 | 0 |
total step counts | 2n + 2 |
- matrix addition
void add() { // 1
int i, j; // 2
for (i = 0; i < rows; i++) // 3
for (j = 0; j < cols; j++) // 4
c[i][j] = a[i][j] + b[i][j]; // 5
} // 6
Statement | steps | frequency | total steps |
// 1 | 0 | 0 | 0 |
// 2 | 0 | 0 | 0 |
// 3 | 1 | rows + 1 | rows + 1 |
// 4 | 1 | rows * (cols + 1) | rows * (cols + 1) |
// 5 | 1 | rows * cols | rows * cols |
// 6 | 0 | 0 | 0 |
total step counts | 2 rows * cols + 2rows + 1 |
4. 점근적 표기법
- 입력의 수 n이 매우 커질 때 알고리즘의 복잡도가 증가하는 패턴을 근사적으로 표현하는 것이다.
- 알고리즘의 성능을 비교하는 데 사용한다.
- n이 매우 증가하는 경우를 가정하여 시간 복잡도의 상한선, 하한선, 상한-하한선의 존재 유무에 따라 O, Ω, θ 등의 기호로 근사적인 복잡도를 표현한다.
- 예를 들어, 두 프로그램의 시간 복잡도가 각각 n² + n, 10n 이라고 가정하자.
n이 작을 땐 계수에 따라 좌우되겠지만, 결국 n이 커질 경우 다항식의 차수가 더 큰 영향을 미친다.
- (n <= 9) n² + n <= 10n
- (n > 9) n² + n > 10n
- 이와 같이 두 개의 시간 복잡도 함수의 실행 명령문의 수가 바뀌는 시점을 분기점이라고 한다.
- 일반적으로 n이 매우 큰 경우의 수행 성능이 더 중요하다.
4-1. Big Oh O
- "상한선"
- n₀ 이상인 모든 n에 대해서 f(n) ≦ c·g(n)을 만족하는 양의 상수 c와 n₀가 존재한다면 시잔 복잡도 함수 f(n) = O(g(n))이라고 표기할 수 있다. 이 반대의 경우도 성립한다.
- f(n) = O(g(n)) 이라고 표기할 수 있다면, 이 알고리즘의 수행 시간이 상한선 c·g(n)을 넘지 않는다는 의미이다.
- (ex1)
- f(n) = 10n + 10,000 ∈ O(n)
- c = 20, n₀ = 1,000 이라고 결정한다면
- f(n) ≦ 20n for all n ≥ 1,000 인 상황에서 Big Oh를 사용할 수 있다.
- (ex2)
- f(n) = n³ + n² + n ∈ O(n)
- c = 3, n₀ = 1 이라고 결정한다면
- f(n) ≦ 3n³ for all n ≥ 1 인 상황에서 Big Oh를 사용할 수 있다.
- c는 최고차항의 계수와 f(n)의 항 수로 결정할 수 있다.
- n₀는 그래프를 통해서 결정할 수 있다.
- O(1) 은 n에 관계없이 항상 일정한 명령어 수 k를 갖는다는 의미이다.
4-2. Big Omega Ω
- "하한선"
- n₀ 이상인 모든 n에 대해서 f(n) ≥ c·g(n) 을 만족하는 양의 상수 c와 n₀가 존재한다면, 시간 복잡도 함수 f(n) = Ω(g(n))이라고 표기할 수 있다. 반대의 경우도 성립한다.
- n₀ 이상인 모든 n에 대해서 f(n)의 수행 시간은 하한선인 c·g(n) 보다 항상 많이 걸린다. 이 알고리즘의 수행 시간은 최소한 하한선 이상으로 걸린다는 의미이다.
4-3. Big Theta θ
- "상한-하한선"
- n₀ 이상인 모든 n에 대해서 c₁·g(n) ≤ f(n) ≤ c₂·g(n) 을 만족하는 양의 상수 c₁, c₂, n₀가 존재한다면, 시간 복잡도 함수 f(n) = θ(g(n))이라고 표기할 수 있다. 반대의 경우도 성립한다.
- n₀ 이상인 모든 n에 대해서 f(n)의 수행 시간은 하한선 (c₁·g(n))과 상한선 (c₂·g(n)) 사이에 존재한다는 의미이다.
4-4. 시간 복잡도 함수의 종류
- O(1) = constant (Fast)
- O(log n) = logarithm
- O(n) = linear
- O(n log n) = log linear
- O(n²) = quadratic
- O(n³) = cubic
- O(2ⁿ) = exponential
- O(n!) = factorial (Slow)
- O(1) ~ O(n²) : 다루기 쉽기 때문에 n이 클 때 유용하다.
- O(2ⁿ) ~ O(n!) : 다루기 어렵기 때문에 n이 아주 작을 때 유용하다.
'Software > Data Structures' 카테고리의 다른 글
[자료구조] 연결 리스트 (0) | 2021.04.20 |
---|---|
[자료구조] 선형 자료구조 (0) | 2021.04.18 |
[자료구조] Recursion 재귀 호출 (0) | 2021.04.17 |
[자료구조] C언어 기초 (0) | 2021.04.17 |
[자료구조] Introduction (0) | 2021.04.17 |