[ALGO] Lect6. 코드블록 단위의 복잡도 분석
교수: 성균관대학교 소프트웨어학과 허재필 교수님
사이트: http://www.kmooc.kr/courses/course-v1:SKKUk+SKKU_46+2021_T1/course/
이번 시간에는 알고리즘에서
코드 블록 단위의 복잡도 분석
의 개념을 배우고, Code Sequence가 있을 때
Motivation
알고리즘을 분석하는 목적은 코드 블록 단위로 다양한 파라미터에 대한 asymptotic run time 혹은 asymptotic memory requirements를 결정하기 위함이다.
■ Asymptotic Behavior of Algorithms
알고리즘의 Asymptotic Behavior이란,
● 예시: 알고리즘 A, B에 대한 complexitiy가 각각 $f_A(n)=Θ(n^2)$, $f_B(n)=Θ(n\log_2n))$인 경우
-
$n=2k$일 때
\[f_A(n) = (2k)^2 = 4k^2\\ f_B(n) = (2k)\log_2(2k) = 2k(\log_2(k)+\log_2(2)) = 2k\log(k)+2k\] -
$n=10k$일 때
\[f_A(n) = (10k)^2 = 100k^2\\ f_B(n) = (10k)\log_2(10k) = 10k(\log_2(k)+\log_2(10)) = 10k\log(k)+33.2k\]
위 예시를 통해 n이 5배가 될 때, $f_A$는 25배로 증가하고 $f_B$는 약 5배로 증가함을 알 수 있다.
Machine Instructions
프로세서(CPU,GPU)는 한정된 숫자의 연산(e.g., 덧셈, 뺄셈, 곱셈, 나눗셈)만을 수행할 수 있다. 이러한 연산을 Instruction이라고 하며,
Constant 수행시간을 갖는 연산
아래의 연산들은 Machine Instruction에 매핑되어있기 때문에 fixed number of cycle에 수행될 수 있다. 즉, Constant 수행시간$Θ(1)$)을 갖는다.
-
Retieving/Storing variables from memory : 메모리로부터 변수 검색 및 저장
-
Variable assignment (=) : 메모리에 특정값 할당
-
Integer Operations (+, -, *, /, %, ++, –) : 덧셈/뺄셈/곱셈/나눗셈 등의 산술 연산
-
Logical Operations (&&, ││, !): AND/OR와 같은 논리 연산
-
Bitwise Operations (&, │, ^, ~)
-
Relational Operations (==, !=, <, <=, =>, >) : 값의 비교
-
Memory Allocation and Deallocation (new, delete) : 메모리 할당
■ 예시1. Swap Algorithm
int tmp = a;
a = b;
b = tmp;
위 알고리즘은 3줄의 코드로 구성되어있지만
■ 예시2. AVL 트리의 노드 재정렬
Tree_node *lrl = left->right->left;
Tree_node *lrl = left->right->right;
parent = left->right;
parent->left = left;
parent->right = this;
left->right = lrl;
left = lrr;
위 알고리즘 역시
시간복잡도의 Dominant Term
가령 어떤 알고리즘이 Θ(1)의 시간복잡도를 갖는 코드와 Θ(n)의 시간복잡도를 갖는 코드로 구성되어있을 때, 이 알고리즘은 Θ(1+n)=Θ(n)의 복잡도를 갖는다고 말한다. 즉, 다항식으로 구성된 시간복잡도는
■ 예시: Θ(n) 시간 복잡도를 갖는 알고리즘
int *Increase_Capacity(int *_array, int _n, int _delta)
{
int *array_old = _array;
_array = new int [_n + _delta];
for(int i=0; i<_n; i++)
_array[i] = array_old[i];
delete[] array_old;
return _array;
}
위 알고리즘은 위의 두 줄과 아래의 두 줄은 모두 Θ(1)의 시간복잡도를 갖지만, 3~4번째 줄(for문)이 machine instruction을 _n회 반복하므로 Θ(n)의 시간복잡도를 갖는다. 따라서 $Θ(1+n+1)=Θ(n)$의 시간복잡도를 갖는 알고리즘이라고 말할 수 있다.
이전에 배웠던
알고리즘 복잡도 분석
프로그램 언어에서 사용하는
■ Control Statement의 종류
- Conditional Statements : if, switch
- Condition-controlled Loops : for, while, do-while
- Count-controlled Loops : for i from 1 to 10 do … end do;
- Collection-controlled Loops : foreach (int i in array) {…}
Conditional Statements
Conditional Statement의 대표적인 예로는
-
condition (test) 에 대한 runtime -
실행될 body 에 대한 runtim
일반적인 condition(e.g., n>5)에 대한 runtime은 Θ(1)이지만,
■ 예시1. Factorial Algorithm
int Factorial(int _n)
{
if( _n == 0)
return 1;
else
return _n * Factorial( _n -1 );
}
_n=0인 조건을 제외하면 언제나 recursive하게 함수를 호출한다는 것을 명확하게 알 수 있다. 따라서 complexity를 비교적 쉽게 계산할 수 있다.
■ 예시2. Find Max Algorithm
template <typename Type>
Type Find_Max(Type *_array, int _n)
{
Type maxVal = _array[0];
for(int i=1; i<_n; i++)
{
if(_array[i] > maxVal)
maxVal = _array[i]; // ·······ⓐ
}
return maxVal;
}
위 코드에서
-
_array가 작은 것부터 큰 것까지 순서대로 정렬된 경우
for문을 돌 때마다 매번 최대값이 갱신되어
ⓐ가 언제나 실행된다. -
_array가 큰 것부터 작은 것까지 순서대로 정렬된 경우
_array[0]이 최대값이므로
ⓐ는 한 번도 실행되지 않는다.
예시2와 같이 데이터의 분포에 따라 코드의 시행횟수가 달라지는 경우가 있기 때문에 이러한 변수까지 고려하여 알고리즘의 complexity를 계산하기는 어렵다. 따라서
Switch
switch문에서 case는 변수가 아닌 상수에 대해서만 프로그래밍이 가능하다. 따라서 미리 정의된 machine instruction에 의해, 바로 해당 값의 binary로 점프할 수 있도록 최적화 되어있기때문에
Conditional-controlled Loops
Conditional-controlled Loop(반복문)의 대표적인 예로는
Conditional-controlled Loop의 runtime은 다음과 같이 구성된다.
-
Initialization 에 대한 runtime -
Condition Check 에 대한 runtime -
Increment 에 대한 runtime
for(i=0; i<n; i++)인 Conditional-controlled Loop에 대한 runtime은 다음과 같다.
- Initialization, Condition Check, Increment에 대한 runtime은 모두 Θ(1)이다.
- body에
break이나return이 없다면, Conditional-controlled Loop는 Ω(n)의 runtime을 갖는다(즉, 최소 n이 소비됨). - body의 runtime이 Θ(f(n))이면, Loop는 Θ(nf(n))의 runtime을 갖는다.
- body의 runtime이 O(f(n))이면, Loop는 O(nf(n))의 runtime을 갖는다 (즉, 최악의 경우 nf(n)이 소비됨)
■ 예시1.
int sum = 0;
for(int i=0; i<n; i++)
{
sum += 1; // Θ(1)
}
위 코드는 $Θ(n·1)=Θ(n)$의 run time을 갖는다.
■ 예시2.
int sum = 0;
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
sum += 1; // Θ(1)
}
위 코드는 $Θ(n·n·1)=Θ(n^2)$의 run time을 갖는다.
■ 예시3.
for(int i=0; i<n; i++)
{
// search through an array of size m
// O(m);
}
위 코드는 $O(n·m)$의 run time을 갖는다.
■ 예시4.
for(int i=0; i<n; i++){ // code which is Θ(f(i,n))}
위 코드의 run time은 다음과 같다.
\[Θ(1 + \sum_{i=0}^{n-1}{(1+f(i,n))})\]■ 예시5.
int sum = 0;for(int i=0; i<n; i++){ for(int j=0; j<i; j++) { sum += i+j; // Θ(1) } // Θ(1+i·1)} // Θ(1+SUMⁿ(1+i·1))
위 코드의 run time은 다음과 같다.
\(Θ(1+\sum_{i=0}^{n-1}{(1+i)}) \\
= Θ(1+n+\sum_{i=0}^{n-1}{i}) \\
= Θ(1+n+\frac{n(n-1)}{2}) \\
= Θ(n^2)\)
Serial Statements
■ 예시1. 적합한 Notation
- $\text{size}=n$인 random list로부터 maximum entry를 찾는 경우에는
모든 값을 조사해야하므로 $\text{run time}=Θ(n)$ 이다. - $\text{size}=n$인 random list로부터 특정값(particular entry)를 찾는 경우
최악의 경우 모든 값을 조사해야하므로 $\text{run time}=O(n)$ 이다.
■ 예시2. leading term 기준으로 Notation 결정
- $O(n) + O(n^2) + O(n^4) = O(n+n^2+n^4) = O(n^4)$
- $O(n) + Θ(n^2) = Θ(n^2)$
- $O(n^2) + Θ(n) = O(n^2)$
- $O(n^2) + Θ(n^2) = Θ(n^2)$
코드에 따라서는 Notation이 섞여있을 수 있다. 이런 경우
Functions
■ 개념
Function(혹은 subroutine)이란
■ Function Call
Function Call을 하면, 어떤 프로그램의 binary로 점프를 하여 해당 부분을 수행한 뒤, 다시 본래의 프로그램 binary위치로 복귀하게 된다. 즉,
- 함수를 구동하기 위한 적절한 환경을 구축한다.
- 함수에 넣어 줄 파라미터를 처리한다.
- subroutine으로 점프한다.
- subroutine을 실행한다.
- return value를 처리한다.
- clean up
위의 일련의 과정은 어떻게보면 Overhead이지만, 최신 프로세서는 이러한 과정을 constant time에 해줄 수 있는 instruction을 가지고 있다. 따라서
■ 함수 안에서 발생하는 run time
함수 안에서 발생하는 run time은 $T_{f(n)}$ 혹은 $T(N)$이라고 표현한다.
References
- [집콕]인공지능을 위한 알고리즘과 자료구조: 이론, 코딩, 그리고 컴퓨팅 사고-비선형 자료구조, K-MOOC: http://www.kmooc.kr/courses/course-v1:SKKUk+SKKU_46+2021_T1/courseware/1158909c057347478d7386a2b7e97214/e9d736660cad4f76bcb9a05974fe0bf2/1?activate_block_id=block-v1%3ASKKUk%2BSKKU_46%2B2021_T1%2Btype%40vertical%2Bblock%4052b62ff6da2147c9a8a65a6056681d91