[알고리즘] Analysis of Algorithm

Analysis of Algorithms

시간복잡도 분석(Time complexity analysis)

- input size에 따라 얼마나 작동하는지 결정.

- CPU, OS, 프로그래밍언어와 독립적임

 

평가지표(Metrics)

Basic operation
- Comparisons, assignments, etc. (비교를 얼마나 했는지, 할당을 얼마나 했는지?)
Input size
- The number of elements in an array
- The length of a list
- The number of columns and rows in a matrix
- The number of vertices and edges in a graph

아무튼 기타 등등 시간복잡도에 영향을 주는 것들?

---

Every-case analysis

배열의 값에 상관없이 항상 같은 횟수의 연산을 실행하는 경우 (= 시간복잡도가 동일함)

T(n) = n인 경우

 

e.g. Addition algorithm for n integers in an array

//배열에서 n개의 정수를 추가하는 알고리즘

number sum (int n, const number S[]) {
	index i;
    number result;
    
    result = 0;
    for(i = 1; i <= n; i++)
    	result = result + S[i];
    return result;
}

e.g. Exchange sort

//교환 정렬 알고리즘
//정렬되어 있어도 동일한 횟수를 진행한다.

void exchangesort(int n, keytype S[]) {
	index i, j;
    for(i = 1; i <= n-1; i++)
    	for(j = i + 1; j <= n; j++)
        	if(S[j] < S[i])
            	exchange S[i] and S[j];
}

- Exchange sort의 시간복잡도 분석

for(i = 1; i <= n-1; i++) 이기 때문에 n-1번 진행함

 

 

 

 

 

 

---

Worst-case analysis

en. 순차검색(Sequential search)

- 기본 동작(S[location] != x)

- 입력 크기 : 배열의 항목 수, n

-> x가 나올 때까지 S[n]을 탐색함 => W(n) = n

=> 분석 불가능

---

Average-case analysis

en. 순차검색(Sequential search)

- 기본 동작(S[location] != x)

- 입력 크기 : 배열의 항목 수, n

- 배열의 각 항목이 서로 다르다고 가정

 

case1 : 항상 x가 S[n]에 있는 경우

 - x가 S[n]에서 k번째 일 확률 -> 1/n

 - x가 k번째이기 위해 필요한 연산의 수 -> k

	S[1]	S[2]	S[k]	S[n]
연산 횟수	1	2	k	n
확률	1/n	1/n	1/n	1/n

case2: x가 S[n]에 있거나 없는 경우

 - x가 S[n]에 있을 확률 p

   -> x가 S[n]의 k번째에 있을 확률 p/n

   -> x가 S[n]의 k번째에 없을 확률 1 - p // 전부 확인해야 없다는걸 알 수 있으니 n(1-p)

if

p = 1 -> A(n) = (n+1)/2

p = 1/2 -> A(n) = 3n/4 + 1/4

 

 

 

---

Best-case analysis

en. 순차검색(Sequential search)

- 기본 동작(S[location] != x)

- 입력 크기 : 배열의 항목 수, n

=> best case는 S[1]에 x가 있는 경우

B(n) = 1

---

알고리즘 분석이란?

-> 알고리즘의 효율성(algorithm analysis)을 분석하는 것

- 수학적 즉명으로 알고리즘의 정확성을 분석할 수 있다.

옳지 않은 알고리즘이란?

- 어떤 input값을 주어도 멈추지 않는 경우?(무한루프?)

- 입력에 대한 오답을 주는 경우

---

알고리즘을 분석하는 방법에는 여러가지가 있고 (Every-case analysis, Worst-case analysis, Average-case analysis, Best-case analysis) 그 중에서 어떤 방식이 필요한가는 상황에 맞춰서 분석하면 되는건가요 교수님?

-> best case는 별로 의미가 없고 worst case가 분석할 때는 유용하다네요. 그리고 every case가 젤 복잡한