02. 자료구조론 Intro (Performance Evaluation)

Performance Analysis

효율적인 알고리즘은 알고리즘을 수행하여 결과를 도출해낼 때까지 걸리는 시간이 짧고, 컴퓨터의 메모리를 적게 사용하는 알고리즘입니다. 

두가지 복잡도를 통해 알고리즘의 성능을 분석할 수 있으며, 이러한 성능분석은 하드웨어에 independent 하게 수행됩니다.

• 시간복잡도 (time complexity) : 알고리즘이 종료될때까지 필요한 시간의 양이며, 이때 절대적인 시간이 아니라 알고리즘이 수행되는데 필요한 연산의 개수를 이용해 측정됩니다.
• 공간복잡도 (space complexity) : 알고리즘이 종료될때까지 필요한 메모리의 양을 나타냅니다.

공간 복잡도 (Space Complexity)

1) C (Fixed space requirements) : 프로그램의 입출력의 개수와 상관없이 고정되게 필요한 메모리의 양으로, 코드를 위한 공간, 단순한 변수나 상수 등에 따른 공간입니다.

2) Sp(I) (Variable space requirements) : 해결하려는 문제의 특정 인스턴스(l)에 의존하는 크기를 갖는 구조화된 변수를 위한 동적인 공간입니다.

이렇게 고정된 공간과 동적인 공간을 이용하여, 총 공간 요구량은 다음과 같게 됩니다.

Total space requirement S(P) = C + Sp(l)

공간복잡도 예시

float rsum(float list[], int n) {
    if (n > 0) return rsum(list, n-1) + list[n-1];
    return 0;
}

배열의 오른쪽부터 더하여 총 합산량을 리턴하는 이 함수의 공간복잡도를 분석해보면 다음과 같습니다.

 

이 알고리즘이 진행될 때, 컴파일러는 함수로 전달되는 인자와, 로컬변수, 그리고 재귀호출마다 리턴 주소를 저장해야 합니다.

해당 알고리즘에서 로컬변수는 사용되지 않습니다.

list[] 를 위해 포인터를 저장해야하므로 4byte가 필요하고,

n을 위한 정수형 4byte,

return address를 위해 또 4byte가 필요합니다.

따라서 각 재귀 호출마다 총 12byte의 메모리가 필요합니다.

만약 배열의 개수 n이 MAX_SIZE라고 한다면 Srsum(MAX_SIZE) = 12 * MAX_SIZE 가 되며, 여기에 고정 공간 요구량 C를 더해주면 해당 알고리즘의 공간복잡도를 도출할 수 있습니다.

 

시간 복잡도 (Time Complexity)

프로그램 P에 의해 수행되는 시간 T(P) 는 컴파일타임과 런타임의 합으로 이루어집니다.

여기서 컴파일타임은 위에서 설명한 공간복잡도의 C, 즉 고정공간요구량과 비슷하게 생각할 수 있습니다.

따라서 시간 복잡도를 고려할때에는 프로그램의 런타임, Tp만을 신경쓰면되며, 이는 프로그램이 동작하면서 수행되는 연산들의 개수를 통해 계산할 수 있습니다.

시간복잡도 예시

float sum(float list[], int n) {
    float tmp_sum = 0;
    for (int i = 0; i < n; i++) {
        tmp_sum += list[i];
    }
    return tmp_sum;
}

위의 코드에서 각 코드가 한번 수행되는데 필요한 연산 수는 두번째 열과 같고, 총 연산 수는 3번째 열과 같습니다.

코드 줄 위치	steps	total steps
2	1	1
3	1	n+1
4	1	n
6	1	1
총 연산 수		2n+3

이때, 3번째 줄은 i = 0 ~ n까지 돌기 때문에 n+1번의 반복이 수행되고, 4번째 줄은 i = 0 ~ n-1까지 돌기 때문에 n번의 반복이 수행되는 것입니다.

---

Asymptotic notation

알고리즘의 복잡도 표기에서 중요하지 않은 상수항이나 계수를 제거하여 나타내어 해당 함수의 증가율에만 집중하는 표기법을 말합니다.

이러한 점근적 표기법은 알고리즘의 복잡도를 단순화하여 나타내기 위해서 특정 함수의 증가 양상을 다른 함수와 비교하여 나타내는 방식입니다. 이러한 표기법에는 Big-O, Big-Ω, Big-Θ 표기법이 있습니다.

셋의 차이는 Big-O 표기법은 알고리즘의 복잡도를 상한선을 기준으로 나타내어서 최악의 경우에도 해당 복잡도보다 같거나 낫다는 것을 나타내고,  Big-Ω 표기법은 하한선을 기준으로 나타내어 최선의 경우 해당 복잡도보다 같거나 안좋다는 것으 나타냅니다. 그리고 Big-Θ 표기법은 둘의 중간을 기준으로 나타냅니다. 

그리고 일반적으로 최악의 경우를 생각하는 것이 좋기 때문에 Big-O 표기법을 가장 많이 사용합니다.

 

Big-O 표기법

f(n) = O(g(n)) iff there exist positive constants c and n0
such that f(n) ≤ c·g(n) for all n, n ≥ n0

g(n) 이라는 어떤 함수에 상수 c를 곱한 함수가 n0라는 특정 수보다 큰 모든 수 n에 대해 항상 f(n)보다 크거나 같게 되는 c와 n0가 존재하면 f(n) = O(g(n)) 이라고 할 수 있다는 뜻입니다. 이때 c와 n0는 임의의 아무 숫자나 상관없이 존재하기만 하면 됩니다.

예를 들어, n = O($n^2$) 라고 나타낼 수 있습니다.

이를 간단하게 증명하자면, n0 = 1, c = 1 이라고 할 때,

$n^2 - n$ ≥ 0 → $n(n-1)$ ≥ 0 을 만족시키는 n의 범위는 n ≥ 1 혹은 0 ≥ n 이므로

 n ≥ 1 인 모든 n에 대해서 n^2 ≥ n 을 만족시키기 때문입니다.

 

하지만 이러한 Big-O 표기법은 얻어진 g(n)이라는 경계가 얼마나 이 알고리즘의 복잡도를 나타내는데 좋은 경계인지는 나타내주지 않습니다.

예를 들어, $f(n) = n$ 일 때, n = O($n^2$), n = O($n^3$), n = O($2^n$) 은 모두 성립합니다.

 

Big-Ω 표기법

f(n) = Ω(g(n)) iff there exist positive constants c and n0
such that f(n) ≥ c·g(n) for all n, n ≥ n0

빅 오메가 표기법은 빅오 표기법과 반대로 g(n)에 상수 c를 곱한 함수가 특정 범위 이후로 f(n)보다 항상 작거나 같게되는 c와 n0가 존재한다는 것을 전제로 하는 표기법입니다.

예를들어 n^2 = Ω(n) 과 같은 것이 있습니다.

하지만 빅 오메가 표기법 또한 경계가 얼마나 좋은 경계인지를 나타내지 않습니다. 그저 구하고자하는 복잡도의 하한선이 된다면 모두 성립하게 됩니다.

추가적으로, Big-O와 Big-Ω 표기법의 정의에서 ≥ 부등호에서 =을 빼고 >, <로 변경하게 되면, Big을 뺀 소문자 O, 소문자 Ω 표기법이 됩니다. 

Big-Θ 표기법

f(n) = Θ(g(n)) iff there exist posi3ve constants c1, c2, and n0
such that c1·g(n) ≤ f(n) ≤ c2·g(n) for all n, n ≥ n0

따라서 위의 두 표기법의 문제를 보완하기 위해 빅 세타 표기법이 존재하는데, 위 정의에서 알 수 있듯이 g(n)은 어떤 상수를 곱하느냐에 따라 f(n)의 상한선, 하한선 모두 될 수 있습니다.

그래서 빅 세타 표기법은 빅오나 빅오메가 표기법보다 더 정확하며, 위에서 언급한 예시와 같은 n = O($2^n$) 나 n^2 = Ω(n) 와 같은 예시는 빅 세타에서는 성립할 수 없게 됩니다.

Big-O 표기법으로 주로 표기되는 시간복잡도의 종류에는 위와 같은 것들이 있습니다. 

아래로 갈수록, n이 커짐에 따라 시간이 기하급수적으로 늘어나게 됩니다.

위 표의 함수들을 그래프로 보면 다음과 같습니다. n이 작을 때에는 각 함수들에 큰 차이가 없지만, 입력값이 커질수록 차이는 점점 커지게 됩니다.