[알고리즘 분석] 01 - 2 알고리즘의 분석(analysis)

알고리즘 분석

 

공간복잡도(space(memory) complexity) 분석

• 입력크기에 따라서 작업공간 (메모리)이 얼마나 필요한 지 결정 하는 절차

시간복잡도(time complexity) 분석

• 입력크기에 따라서 단위연산이 몇 번 수행되는지 결정하는 절차
• 알고리즘이 수행되는 기계에 따라 문제를 해결하는 시간이 달라 짐.

우리의 관심도

시간복잡도 > 공간복잡도

 

시간복잡도분석의 기준

• 기계에 독립적인, 문제 본연의 복잡도를 표현하여야 함.

표현 척도

- 단위연산(basic operation)

• 비교문(comparison), 지정문(assignment) 등

- 입력크기(input size)

• 배열의 크기, 리스트의 길이, 행렬에서 행과 열의 크기, 트리에 서 마디와 이음선의 수

분석 방법의 종류

1. Every-case analysis
2. Worst-case analysis
3. Average-case analysis
4. Best-case analysis

모든 경우 분석(every-case analysis)

• 입력크기에만 종속. 입력값과는 무관
• 입력 값과는 무관하게 결과 값은 항상 일정 

최악의 경우 분석(worst-case analysis)

• 입력크기와 입력값 모두에 종속
• 단위연산이 수행되는 횟수가 최대인 경우 선택

평균의 경우 분석(average-case analysis)

• 입력크기에 종속
• 모든 입력에 대해서 단위연산이 수행되는 기대치(평균)
• 각 입력에 대해서 확률 할당 가능
• 일반적으로 최악의 경우보다 계산이 복잡

최선의 경우 분석(best-case analysis)

• 입력크기와 입력 값 모두에 종속
• 단위연산이 수행되는 횟수가 최소인 경우 선택

Discussion

- 우리의 주요 관심은

• Worst-case analysis
• 비관적 시각으로 알고리즘을 고안

- 평균시간 개념의 비현실성

• 핵발전소 통제 알고리즘의 평균소요시간

조건: 위험 감지 시 통제 알고리즘이 안전을 위해 2초 이내 수행되어야 한다

• 99%는 1초 소요
• 1%는 10초 소요
• 평균 1.09초 소요
• 이 알고리즘을 핵발전소에서 사용할 수 있을까?

*사용이 어렵다... 안전상의 문제 발생(최악의 경우를 좋게하는게 중요)

 

Alg 1.2 배열의 수 더하기

문제: n개의 수로 된 배열 S에 있는 모든 수를 더하라

입력: 양의 정수 n, 수의 배열 S(첨자는 1부터 n)

출력: S에 있는 수의 합, sum

배열덧셈 시간복잡도 분석

단위연산: 덧셈

입력크기: 배열의 크기 n

모든 경우 분석:

• 배열 내용에 상관없이 for루프가 n번 반복된다.
• 각 루프마다 덧셈이 1회 수 행된다.
• 따라서, n에 대해서 덧셈이 수행되는 총 횟수는 T(n) = n 이다.

단위연산: 지정문 (for-루프의 첨자 지정문 포함)

입력크기: 배열의 크기 n

모든 경우 분석:

• 배열 내용에 상관없이 for루프가 n번 반복된다.
• 따라서, 지정문이 T(n) = n + n + 1번 수행된다.

Alg 1.3 교환정렬

문제: 비내림차순(nondecreasing order)으로 n개의 키를 정렬하라

입력: 양의 정수 n, 키의 배열 S(첨자는 1부터 n)

출력: 키가 비내림차순으로 정렬된 배열 S

교환정렬 시간복잡도 분석

단위연산: 조건문 (S[j]와 S[i]의 비교)

입력크기: 정렬할 항목의 수 n

모든 경우 분석:

• j-루프가 수행될 때마다 조건문 1번씩 수행
• 조건문의 총 수행횟수

따라서 T(n)= (𝑛 − 1) + (𝑛 − 2) + … + 1 = (𝑛−1) 𝑛 / 2

 

교환정렬 시간복잡도 분석

단위연산: 교환하는 연산 (exchange S[j] and S[i])

입력크기: 정렬할 항목의 수 n

최악의 경우 분석:

조건문의 결과에 따라서 교환 연산의 수행여부가 결정된다.

최악의 경우 = 조건문이 항상 참(true)이 되는 경우

= 입력 배열이 거꾸로 정렬되어 있는 경우

W(n) = (n - 1) n / 2

(예) 5, 4, 3, 2, 1

행렬곱셈 시간복잡도 분석

단위연산: 가장 안쪽 for 루프에 있는 곱셈

입력크기: 행과 열의 개수 n

모든 경우 분석:

• for i루프는 항상 n번 수행. for i 루프 한 번 수행될 때마다 for j 루프는 항상 n번 수행
• for j 루프 한 번 수행될 때마다 for k 루프는 항상 n번 수행

T(n) = n× n× n = n^3

*반드시 단위연산을 무엇으로 했는지 언급해야한다.

 

순차검색 시간복잡도 분석 (최악)

단위연산: 배열의 아이템과 키 x와 비교 연산 (S[location] != x)

입력크기: 배열 안에 있는 아이템의 수 n

최악의 경우 분석:

• x가 배열의 마지막 아이템이거나, x가 배열에 없는 경우 단위 연산이 n번 수행된다.
• 따라서, W (n) = n

순차검색 알고리즘의 경우 입력배열의 값에 따라서 검색하는 횟수가 달라지므로, 모든 경우 분석은 불가능하다.

순차검색 시간복잡도 분석 (평균)

단위연산: 배열의 아이템과 키 x와 비교 연산 (S[location] != x)

입력크기: 배열 안에 있는 아이템의 수 n

평균의 경우 분석:  배열의 아이템이 모두 다르다고 가정한다.

 - 경우 1: x가 배열 S안에 있는 경우만 고려

 - 1 <= k <= n 에 대해서 x가 배열의 k번째 있을 확률

x가 배열의 k번째 있다면, 이를 찾기 위해서 수행하는 단위 연산의 횟수 = k

따라서,

 - 경우2: x가 배열 S안에 없는 경우도 고려

 - x가 배열 S안에 있을 확률을 p라고 하면,

• x가 배열의 k번째 있을 확률 = p / n
• x가 배열에 없을 확률 = 1 - p

 - 따라서,

순차검색 시간복잡도 분석 (최선)

단위연산: 배열의 아이템과 키 x와 비교 연산 (S[location] != x)

입력크기: 배열 안에 있는 아이템의 수 n

최선의 경우 분석:

• x가 S[1]일 때, 입력의 크기에 상관없이 단위연산이 1번만 수행 된다.
• 따라서, B(n) =1

 

Discussion

• 최악, 평균, 최선의 경우 분석 방법 중에서 어떤 분석이 가장 정 확한가? 답이 어려움
• 최악, 평균, 최선의 경우 분석 방법 중에서 어떤 분석을 사용할 것인가? 경우에 따라 다름 / 최악의 경우가 중요함
• 복잡도 함수(complexity function)는 음이 아닌 정수가 주어지면 음이 아닌 실수를 내주는 함수
• f(n) = n, lg n, 3n^2+ 4^n etc.

정확도(correctness) 분석

- 알고리즘이 의도한 대로 수행되는지를 증명하는 절차

- 정확도를 증명하는 것은 쉽지 않음

- 정확한 알고리즘이란?

• 어떠한 입력에 대해서도 답을 출력하면서 멈추는 알고리즘

- 정확하지 않은 알고리즘이란?

• 어떤 입력에 대해서 멈추지 않거나, 또는
• 틀린 답을 출력하면서 멈추는 알고리즘