알고리즘의 분석(analysis) 공간적 효율성(Space Efficiency)과 시간적 효율성(Time Efficiency) 공간적 효율성은 얼마나 많은 메모리 공간을 요하는가를 지칭 시간적 효율성은 얼마나 많은 시간을 요하는가를 지칭 효율성을 뒤집어 표현하면 복잡도(Complexity)가 된다. 즉, 복잡도가 높을수록 효율성은 저하된다. 일반적으로 시간적 효율성이 공간적 효율성보다 더욱 강조가 됨 Why? Time Cost 가 Memory Cost 보다 비싸기 때문 시간적 효율성은 CPU의 성능과 직결됨 Multi-core... 슈퍼 컴퓨터, 클러스터 컴퓨터... 가격대비 효율... 공간적 효율성은 메모리의 용량과 직결됨 Shared (Distributed) Memory Cloud Computing... 그렇다고, 공간적 효율을 무시하면 안됨

알고리즘의 분석(analysis) 시간적 복잡도 (Time Complexity) 분석 하드웨어 환경에 따라 처리시간이 달라진다. 부동소수 처리 프로세서, GPU (Graphics Processing Unit) 존재유무 곱셈/나눗셈 가속기능 유무 입출력 장비의 성능, 공유여부 소프트웨어 환경에 따라 처리시간이 달라진다. 프로그램 언어의 종류, 운영체제, 컴파일러의 종류 운영체제에 현재 어느 정도의 프로세스가 동작하고 어느 정도의 load가 걸리고 있는가? 이러한 환경적 차이로 인해 실제 작동시간을 통한 분석이 어렵다. 그래서, 실행환경과 무관하게 개략적으로 분석하는 방법 필요

알고리즘의 분석(analysis) 그래서… 시간복잡도(Time Complexity) 분석이란? 표현 척도 입력 크기에 따라서 단위 연산이 몇 번 수행되는지 결정하는 절차 표현 척도 단위연산(basic operation) 비교문(comparison)에 있는 비교 연산 지정문(assignment)에 있는 수치연산 후 지정 연산 등… 알고리즘을 수행하는 데 있어서 가장 핵심적인 역할을 담당하는 연산 입력크기(input size) 배열의 크기, 리스트의 길이, 행렬에서 행과 열의 크기 그래프/트리에서 Vertex와 Edge의 수

분석 방법의 종류 (1/3) 최악의 경우 분석(Worst-case analysis) 입력 크기와 입력 값 모두에 종속(dependent) 단위연산이 수행되는 횟수가 최대(최악)인 경우 선택 표기 방법: W(n) 예: 입력 값이 찾는 대상인 리스트에 존재하지 않을 때 최선의 경우 분석(Best-case analysis) 입력 크기와 입력 값 모두에 종속 표기 방법: B(n) 단위 연산이 수행되는 횟수가 최소(최선)인 경우 선택

분석 방법의 종류 (2/3) 평균의 경우 분석(Average-case analysis) 입력 크기와 입력 값 모두에 종속 모든 입력에 대해서 단위연산이 수행되는 횟수의 기대치(평균) 표기 방법: A(n) 확률적 계산 필요 각 입력 값에 대해서 확률 할당이 다를 수 있음  확률에 따라 기대치가 다르게 계산될 수 있음  예를 들어, 1~100까지 수의 정렬된 배열에 대한 이진검색인 경우 찾으려는 입력(키)값이 90보다 큰 경우가 더 많다면 평균 단위연산 수행 횟수는 일반적인 경우 (입력 값이 골고루 분포되는 경우)와 다르다. 일반적으로 최악의 경우보다 계산이 복잡

분석 방법의 종류 (3/3) 모든 경우 분석(Every-case analysis) 복잡도는 입력 크기에만 종속적임 입력 값의 내용과 무관(independent)하게 복잡도가 항상 일정한 경우에만 모든 경우 분석이 가능함 즉, 모든 경우 분석이 가능하다면 최악, 최선, 평균의 경우가 모든 경우 분석결과와 동일함 표기 방법: T(n) 예: 입력 데이터 값들에 대한 평균을 구하라. T(n)이 존재하면 W(n) =A(n)=B(n) =T(n)

[알고리즘 1.1] 시간 복잡도 분석(1/5) [알고리즘 1.1] 문제: 크기가 n인 리스트 (배열) S에 x가 있는가? 입력(파라미터): (1) 양수 n, (2) 배열 S[1..n], (3) 키 x 출력: x가 S의 어디에 있는지의 위치, 만약 없으면 0 index seqsearch(int n, // 입력(1) keytype[] S, // 입력(2) keytype x) // 입력(3) { index location; location = 1; while (location <= n && S[location] != x) location++; if (location > n) location = 0; return location; }

[알고리즘 1.1] 시간 복잡도 분석(2/5) 단위연산: 배열의 아이템과 키 x와 비교 연산 (S[location] != x) 최악의 경우 분석: x가 배열의 마지막 아이템이거나, x가 배열에 없는 경우 단위 연산이 n번 수행된다. 따라서,

[알고리즘 1.1] 시간 복잡도 분석(3/5) 단위연산: 배열의 아이템과 키 x와 비교 연산 (S[location] != x) 가정:배열의 아이템이 모두 다르다. 평균의 경우 분석(경우 1): x가 배열 S안에 있는 경우만 고려 에 대해서 x가 배열의 k번째 있을 확률 = 1/n x가 배열의 k번째 있다면, x를 찾기 위해서 수행하는 단위연산의 횟수 = k 따라서,

[알고리즘 1.1] 시간 복잡도 분석(4/5) 평균의 경우 분석(경우 2): x가 배열 S안에 없는 경우도 고려 x가 배열 S안에 있을 확률을 p라고 하면, x가 배열에 있을 확률 = p (x가 배열의 k번째 있을 확률 = p/n) x가 배열에 없을 확률 = 1 – p 따라서, 참고:

[알고리즘 1.1] 시간 복잡도 분석(5/5) 단위연산: 배열의 아이템과 키 x와 비교 연산 (S[location] != x) 최선의 경우 분석: x가 S[1]과 동일할 때, 입력의 크기에 상관없이 단위연산이 1번만 수행된다. 따라서, B(n) = 1 순차검색 알고리즘의 경우 입력배열의 값 및 찾으려는 키 값에 따라서 검색하는 횟수가 달라지고 W(n) ≠A(n) ≠ B(n) 므로, 모든 경우(every-case)의 시간 복잡도 분석은 불가능하다.

[알고리즘 1.2] 시간 복잡도 분석(1/2) [알고리즘 1.2] 문제: 크기가 n인 배열 S의 모든 수를 더하라. 입력: 양수 n, 배열 S[1..n] 출력: 배열 S에 있는 모든 수의 합 모든 경우 분석이 가능하면 최악, 평균, 최선 분석은 필요 없다. number sum (int n, number[] S) { index i; number result; result = 0; for (i = 1; i <= n; i++) result = result + S[i]; return result; }

[알고리즘 1.2] 시간 복잡도 분석(2/2) 단위연산: 덧셈 입력크기: 배열의 크기 n 모든 경우 분석: 배열 내용에 상관없이 for-루프가 n번 반복된다. 각 루프마다 덧셈이 1회 수행된다. 따라서, n에 대해서 덧셈이 수행되는 총 횟수는 T(n) = n 이다. 단위연산: 지정문 (for-루프의 첨자 지정문 포함) 입력크기: 배열의 크기 n 모든 경우 분석: 배열 내용에 상관없이 for-루프가 n번 반복된다. 따라서, 지정문이 T(n) = n + n + 1번 수행된다. 단위 연산을 다르게 택함으로써, 시간 복잡도가 다르게 나왔다.  그러나, (추후에 배우겠지만) 사실 둘 모두는 같은 복잡도 카테고리에 속한다.

[알고리즘 1.3] 시간 복잡도 분석(1/4) [알고리즘 1.3] 문제: 비내림차순(nondecreasing order)으로 n개의 키를 정렬 입력: 양수 n, 배열 S[1..n] 출력: 비내림차순으로 정렬된 배열 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]; }

[알고리즘 1.3] 시간 복잡도 분석(2/4) 단위연산: 비교문 (S[j]와 S[i]의 비교) 입력크기: 정렬할 항목의 수 n 모든 경우 분석: j-루프가 수행될 때마다 조건문을 1번씩 수행 조건문의 총 수행횟수 i = 1 : j-루프 n – 1 번 수행 i = 2 : j-루프 n – 2 번 수행 i = 3 : j-루프 n – 3 번 수행 i = n – 1 : j-루프 1 번 수행 따라서

[알고리즘 1.3] 시간 복잡도 분석(3/4) 단위연산: 교환하는 연산 (exchange S[j] and S[i]) 최악의 경우 분석: 조건문의 결과에 따라서 교환 연산의 수행여부가 결정된다. 최악의 경우 = 조건문이 항상 참(true)이 되는 경우 = 입력 배열이 거꾸로 정렬되어 있는 경우  교환연산은 for 루프 안에서 항상 수행 따라서,

[알고리즘 1.3] 시간 복잡도 분석(4/4) 단위연산: 교환하는 연산 (exchange S[j] and S[i]) 최선의 경우 분석: 조건문의 결과에 따라서 교환 연산의 수행여부가 결정된다. 최선의 경우 = 조건문이 항상 거짓(true)이 되는 경우 = 입력 배열이 완전 정렬되어 있는 경우  교환연산은 발생하지 않음 따라서, [교훈] 단위연산을 무엇으로 정하는지에 따라 분석 방법에 대한 결정 및 그 결과가 달라질 수 있다.

[알고리즘 1.4] 시간 복잡도 분석(1/2) [알고리즘 1.4] 문제: 두개의 nn 행렬의 곱을 구하라. 입력: 양수 n, 수의 2차원 배열 A 와 B (둘 다 nn 행렬) 출력: A와 B의 곱이 되는 수의 2차원 배열 C (nn 행렬) void matrixmul (int n, number[][] A, number[][] B, number[][] C) { index i, j, k; for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) { C[i][j] = 0; for (k = 1; k <= n; k++) C[i][j]=C[i][j]+A[i][k]*B[k][j]; }

[알고리즘 1.4] 시간 복잡도 분석(2/2) T(n)이 존재하므로 W(n)=T(n) 단위연산: 가장 안쪽 for 루프에 있는 곱셈 입력크기: 행과 열의 개수, 즉 n 모든 경우 분석: i-루프는 n 번 수행 i-루프가 수행될 때마다 j-루프가 n 번 수행 j-루프가 수행될 때마다 k-루프가 n 번 수행 단위 연산은 k-루프 안에 존재 따라서, 최악의 경우 분석: T(n)이 존재하므로 W(n)=T(n)

[알고리즘 1.5] 시간 복잡도 분석(1/2) [알고리즘 1.5] 문제: 크기가 n인 정렬된 배열 S에 x가 있는가? 입력: (1) 양수 n, (2) 배열 S[1..n], (3) 키 x 출력: x가 S의 어디에 있는지의 위치, 만약 없으면, 0 index binsearch(int n, // 입력(1) keytype[] S, // 입력(2) keytype x) // 입력(3) { index location, low, high, mid; low = 1; high = n; location = 0; while (low <= high && location == 0) { mid = (low + high) / 2; if (x == S[mid]) location = mid; else if (x < S[mid]) high = mid – 1; else low = mid + 1; } return location;

[알고리즘 1.5] 시간 복잡도 분석(2/2) 단위연산: 배열의 아이템과 키 x와 비교 연산 (x == S[mid]) 입력크기: 배열 안에 있는 아이템의 수 n 최악의 경우 분석: x가 배열의 마지막 아이템이거나, x가 배열에 없는 경우 단위 연산이 단위 연산이 log2 n + 1번 수행된다. 따라서,

시간 복잡도: 어떤 것을 사용하지? 정한 단위연산에 대하여 최악, 평균, 최선의 경우가 구별이 가지 않는 경우는 모든 경우 분석을 수행 만약 최악, 평균, 최선의 경우가 구별이 된다면…  응용에 따라 다르나, 대개 최악 분석을 사용한다. Why?...

알고리즘의 다른 관점에서의 분석-정확도 분석 알고리즘이 의도한 대로 수행되는지를 증명하는 절차 (즉, 알고리즘이 정확하게 수행되는지를 증명하는 절차) 정확한 알고리즘이란? 어떠한 입력에 대해서도 올바른 답을 출력하면서 멈추는 알고리즘 정확하지 않은 알고리즘이란? 어떤 입력에 대해서 멈추지 않거나, 또는 틀린 답을 출력하면서 멈추는 알고리즘 정확도 분석은 프로그램 증명(Program Verification)과 마찬가지로 매우 이론적인 분야로서, Dijkstra 등에 의해서 연구되었다.

알고리즘의 점근적 복잡도 동일 문제 해결을 위한 알고리즘 A와 B를 생각해 보자 아래와 같은 A와 B 의 Complexity라면 A가 당연히 효율적 A: n B: n2 그러나, 아래와 같은 A와 B 라면? A: 100n B: 0.01n2 입력의 크기가 10,000 보다 적으면 알고리즘 A가 좋고 그렇지 않으면 알고리즘 B가 좋다. 그렇다면 어느 알고리즘이 더 좋은 것인가? Asymptotic Complexity (점근적 복잡도) 일반적으로 시간적 효율을 말할 때에는 n이 무한히 큰 경우일 때의 복잡도를 지칭한다. 즉, 입력 데이터의 크기 n이 무한대로 갈 때 알고리즘의 실행시간이 어디에 접근하는가?

알고리즘의 점근적 복잡도와 차수 상수(Constant) vs. 차수(Order) Comparing c1n with c2n2 (c1 and c2 are constants) Regardless of c1 and c2, there exists a break even point. Consequently … 차수(Order) is important 상수(Constant) can be negligible 즉, N이 무한대로 갈 때인 Asymptotic Complexity를 기준으로 평가한다. 입력 데이터가 최악일 때 알고리즘이 보이는 효율 기준 c2n2 c1n break even point

대표적인 복잡도 카테고리 (lg n): 로그(logarithmic) (n): 1차(linear) (n lg n) (n2): 2차(quadratic) (n3): 3차(cubic) (2n): 지수(exponential) (n!): factorial

복잡도 함수의 증가율

시간 복잡도별 실제 실행 시간 비교 [가정]단위 연산 1회 수행시간 = 10-9 second