Internet Computing Laboratory @ KUT Youn-Hee Han 8장. 알고리즘과 효율 Internet Computing Laboratory @ KUT Youn-Hee Han

1. 알고리즘 건포도 케이크 만들기 알고리즘 케이크: 출력 재료: 입력 그릇, 오븐, 요리사: 하드웨어 추상적, 개략적으로 기술한 조리법 알고리즘을 구체적으로 표현한 것이 프로그램 알고리즘 단어 유해 19세기 페르시어 수학자 Mohammed Al Khowarizmi가 십진수의 사칙연산 방법을 단계적으로 기술하한 것에서 유래 [Definition from Wikipedia] an algorithm is a procedure (a finite set of well-defined instructions) for accomplishing some task which, given an initial state, will terminate in a defined end-state Data Structure

1. 알고리즘 상세성 수준 알고리즘은 추상적, 프로그램은 구체적 알고리즘의 특성 Level of Detail cf. Level of Abstraction 기본 동작을 언급하되 너무 추상적이거나 너무 구체적이어서는 안된다. 알고리즘은 추상적, 프로그램은 구체적 알고리즘은 구현과 무관하게 추상적으로 기술되는 반면에 프로그램은 구현 환경과 연관되어 기술된다. 알고리즘을 기술할 때에는 “이 정도 기술하면 프로그램 작성시에 구현 환경에 맞도록 잘 코딩할 것이다.” 라는 가정이 내재해 있다. 알고리즘의 특성 Input, Output, Definiteness (정확&명확성), Finiteness(유한성), Effectiveness Data Structure

4. 알고리즘의 효율 공간적 효율성(Space Efficiency)과 시간적 효율성(Time Efficiency) 공간적 효율성은 얼마나 많은 메모리 공간을 요하는가를 말한다. 시간적 효율성은 얼마나 많은 시간을 요하는가를 말한다. 효율성을 뒤집어 표현하면 복잡도(Complexity)가 된다. 복잡도가 높을수록 효율성은 저하된다. 일반적으로 시간적 효율성이 공간적 효율성보다 더욱 강조가 됨 시간적 복잡도 (Time Complexity) 분석 하드웨어 환경에 따라 처리시간이 달라진다. 부동소수 처리 프로세서 존재유무, 나눗셈 가속기능 유무 입출력 장비의 성능, 공유여부 소프트웨어 환경에 따라 처리시간이 달라진다. 프로그램 언어의 종류 운영체제, 컴파일러의 종류 운영체제에 현재 어느 정도의 load가 걸리고 있는가? 이러한 환경적 차이로 인해 분석이 어렵다. Data Structure

4. 알고리즘의 효율 시간적 복잡도를 측정하는 방법 복잡도 분석 기준 to do our measurements analytically, not experimentally. In other words we will analyze the algorithm or the relevant aspects of a program implementing it Most commonly, we measure one of the following: the number of additions, multiplications etc. (for numerical algorithms). the number of comparisons (for searching, sorting) the number of data moves (assignment statements,maybe also parameters). the amount of memory required. 복잡도 분석 기준 실행환경과 무관하게 개략적으로 분석 입력 데이터의 수 = 데이터 크기(Size) = N 실행에 걸리는 시간을 N의 함수 로 표시 – f(N) N이 무한대로 갈 때의 효율을 표시함으로써 환경적 변수에 의한 영향이 무시됨 Data Structure

4. 알고리즘의 효율 연결 리스트 데이터 N 개를 출력하는 함수 복잡도를 구하는 예 할당 한번 시간을 a, 비교 한번 시간을 b, 출력 한번 시간을 c라고 가정 정확한 총 실행시간은 a(N+1) + bN + cN = (a+b+c)N + a a, b, c 계수 값은 실행환경에 따라 달라진다. 일반적으로… 단순히 “실행시간이 N에 비례”하는 알고리즘이라고 말함. 실행환경에 따른 계수는 무시해버린다. void Display(Nptr Head) {          Nptr Temp = Head;       while (Temp != NULL) {   printf("%d", Temp->Data);       Temp = Temp->Next;   } } Data Structure

4. 알고리즘의 효율 동일 문제 해결을 위한 알고리즘 A와 B를 생각해 보자 아래와 같은 A와 B 의 Complexity라면 A가 당연히 효율적 A는 ‘N에 비례’ B는 ‘N^2에 비례’ 그러나, 좀 더 정확히 표현하여 아래와 같은 A와 B 라면? A는 1500N B는 2N^2 위와 같은 현상은 실행환경에 따른 변수인 계수 값을 무시하지 않는다면 어느 정도 작은 N에 대하여 B가 더 효율적 그렇다면 어떤 방법을 이요애야 하나? Asymptotic Complexity (점근적 복잡도) 일반적으로 시간적 효율을 말할 때에는 N이 무한히 큰 경우로 국한 즉, ‘입력 데이터의 크기 N이 무한대로 갈 때 알고리즘의 실행시간이 어디에 접근하는가?’ Data Structure

4. 알고리즘의 효율 입력 크기에 따른 함수값 비교 logN < N < NlogN < N2 < N3 < ... < N! < NN Data Structure

4. 알고리즘의 효율 1000 MIPS 컴퓨터의 연산시간 MIPS = Millions of Instructions per Second   1.3N3 10N2 47NlgN 48N 연산시간 N = 1,000 1.3 sec 10 msec 0.4 msec 0.048 msec N = 10,000 22 min 1 sec 6 msec 0.48 msec N = 100,000 15 day 1.7 min 78 msec 4.8 msec N = 1,000,000 41 year 2.8 hours 0.94 sec 48 msec N = 10,000,000 41,000 year 1.7 week 11 sec .48 sec Data Structure

4. 알고리즘의 효율 10의 승수변화에 따른 시간 Micro-scale, Macro-scale 초속(m/sec) 102 103 104 105 106 107 108 109 1010 .. 1017 시간 1.7 분 17분 2.8 1.1 일 1.6 주 3.8 달 3.1 년 31 310 우주나이 초속(m/sec) 해당속도해당속도 예 10-10 3cm/10년 대륙의 표류 10-8 30cm/년 머리카락 생장 10-6 8.6cm/일 빙하 이동 10-4 37cm/시간 장 운동 10-2 62cm/분 개개미 1 3.5km/시 인간 걸음 102 352km/시 비행기 프로펠러 104 592km/분 우주 왕복선 106 992km/초 지구 공전 108 99,200km/초 광속의 1/3 Data Structure

4. 알고리즘의 효율 데이터 N 개 짜리의 정렬되지 않은 배열에서 어떤 레코드를 찾기 알고리즘의 실행시간 처음부터 원하는 키를 가진 레코드가 나올 때까지 순차적으로 읽음. 효율은 키 값의 비교 횟수를 기준으로 평가됨. 세 가지 경우 최선의 경우: 운이 좋으면 첫 번째 데이터가 찾고자 하는 것. 비교 1번 최악의 경우: 배열 끝에 찾고자 하는 것, 비교 N 번. 평균적 경우: 대략 배열의 반 정도만에 찾음. N/2 번 비교 알고리즘의 실행시간 데이터 개수 N의 함수, 데이터의 분포 특성의 함수 최선의 경우(Best Case)가 나오기를 기대하기는 어렵다. 무작위로 분포하기 때문에 평균적인 경우를 정의하기 어렵다. 효율 분석은 항상 최악의 경우(Worst Case)를 기준으로 말함. 최악의 데이터가 들어오더라도 이 시간이면 실행한다고 말하는 것이 안전 실제 효율이 최소한 그보다는 좋음. Data Structure

4. 알고리즘의 효율 시간적 복잡도 구하는 법에 관한 요약 데이터 크기 N의 함수로 표시하되 계수를 무시한다. N이 무한대로 갈 때를 기준으로 평가한다. 입력 데이터가 최악일 때 알고리즘이 보이는 효율을 기준으로 한다. 위와 같은 조건을 전제로 효율을 분석하기 위해 사용되는 수학적 도구가 빅 오(Big Oh) 기호 Big Oh의 해석 데이터 N이 충분히 클 때, 어떤 함수 f(N)이 원래 함수 g(N)보다 크다면 f(N)를 해당 알고리즘의 Big Oh 효율로 본다. c 변수의 역할 큰 c 값을 내세움으로써 g 함수의 실행환경에 따른 자질구레한 계수를 무시해 버리기 위함 임의의 상수 N0와 c가 있어서 N≥N0인 N에 대해서 g(N)  c⋅f(N) 이 성립하면 g(N)  O(f(N)) Data Structure

4. 알고리즘의 효율 Big Oh Example 1 Big Oh Examples g(N) = 2N + 5라면 이 알고리즘은 O(N)이다. (O(N)에 속한다.) 알고리즘의 효율을 나타내는 O( )의 괄호 안에 들어가는 함수 f(N) = N이다. N이 충분히 커서 1000보다 크다면  g(N)  3⋅f(N) 이 항상 성립한다. N이 1000이라면 벌써 3⋅f(N) = 3⋅N = 3000이고, g(N) = 2⋅1000 + 5 = 2005에 불과하기 때문이다. 이 경우의 N0는 1000, c는 3에 해당한다. Big Oh Examples 210N2 + 90N + 200  O(N2) since 210N2 + 90N + 200 ≤ 9000N2 for N ≥ 8000 10N3 + 40N2 + 90N + 200  O(N3) since 10N3 + 40N2 + 90N + 200 ≤ 1000N3 for N ≥ 10000 10n + 5 log(n) + 8  O(n) 65  O(1) Big Oh 구하는 약식 방법 주어진 함수의 가장 높은 차수의 항만 끄집어내되 계수를 1로 하면 됨 Data Structure

4. 알고리즘의 효율 Big Oh 기호는 실행시간의 상한(Upper Bound) 이면서 동시에 Tight Upper Bound 를 나타냄 5N + 15 = O(N) since 5N + 15 ≤ 1000N for N ≥ 200 5N + 15 = O(N2) since 5N + 15 ≤ 100N2 for N ≥ 2000 그러나 Tight Upper Bound의 개념으로 5N + 12는 O(N)이 Tight Upper Bound이다. Quadratic Time Algorithm (제곱시간 알고리즘) 2 ((N-1)-2+1) N = O(N2) 실행시간이 데이터 개수의 제곱에 비례하는 알고리즘 for i = 1 to N    for  j = 2 to (N-1)      do { Read A[i, j];           Write A[i, j];       } Data Structure

4. 알고리즘의 효율 Linear Time Algorithm (선형시간 알고리즘) (N-19001)⋅(MAX - 1)⋅2 = O(N) Constant Time Algorithm (상수시간 알고리즘) 두 번 실행 2 = 2N0 = O(N0) = O(1) 데이터 수 N에 무관하게 상수 번 수행되는 알고리즘 #define MAX 9000000 for i = 1000 to N-20000     for  j = 2 to MAX         do {             Read A[i, j];              Write A[i, j];           } x = 20; printf("%d", x); Data Structure

4. 알고리즘의 효율 Exponential Time Algorithm (지수시간 알고리즘) O(aN) 사실상 컴퓨터로 실행하기 불가능할 정도의 많은 시간을 요하는 알고리즘 Logarithmic Time Algorithm (로그 시간 알고리즘) O(logN)으로서 O(N)보다 매우 빠른 알고리즘 로그함수의 밑수(Base)는 아무렇게나 표시 logbN = logN / logb = (1/logb)⋅logN . 빅 오 기호에서 계수는 무시 O(logbN) = O(logN) 기타사항 - log2N을 lgN으로 표시 Data Structure

4. 알고리즘의 효율 if statement가 있을 때의 효율 측정 여러 부분로 나눌 수 있는 알고리즘인 경우 최악의 경우에 대해서 평가: O(N2) 여러 부분로 나눌 수 있는 알고리즘인 경우 첫 부분 – O(N2), 두번째 부분 – O(N), 세번째 부분 – O(N3) O(N2 + N + N3) = O(N3) 가장 속도가 느린 부분이 전체적인 효율을 좌우하는 Dominant Factor가 됨 if (x = = 1) { for i = 1 to N       for  j = 2 to (N-1)           do {           Read A[i, j];               Write A[i, j];           } } else { x = 20;   printf("%d", x); } Data Structure

5. 효율 분석의 예 리스트의 삽입,삭제에 대한 효율 1) 리스트내에 레코드 수를 추적하는 변수가 별도로 있으면 O(1) 2) 정렬 안된 것과 정렬된 것에 따라 달라짐 정렬된 것일 때 삽입위치를 찾기 위해 이진 탐색을 이용하면 O(lgN) 삽입위치를 찾는 작업 + 데이터 이동 작업 O(N)+O(N)=O(N) 또는 O(lgN) + O(N)=O(N) 3) 사용자가 위치를 직접 지정하여 삽입 배열인 경우… O(1)+O(N)=O(N)   배열로 구현 연결 리스트로 구현 1) Find List Length O(1) / O(N) 2) Insert an Item 3) Insert an Item at ith Position O(N) Data Structure

5. 효율 분석의 예 이진탐색 비교회수 탐색시간 비교 N 선형탐색 이진탐색 10 110 4,322 100 1,010 7,644 비교 한번에 데이터 크기가 64, 32, 16, 8, 4, …, 1 총 비교회수는 대략 lgN 번 효율 – O(logN) 탐색시간 비교 선형탐색 10N + 10, 이진탐색 1000lgN + 1000 N 선형탐색 이진탐색 10 110 4,322 100 1,010 7,644 1,000 10,010 10,966 10,000 100,010 14,288 100,000 1,000,010 17,610 1,000,000 10,000,010 20,932 Data Structure