(Program = Algorithm + Data Structure)

Presentation on theme: "(Program = Algorithm + Data Structure)"— Presentation transcript:

1 (Program = Algorithm + Data Structure)
프로그램 = 알고리즘 + 자료구조 (Program = Algorithm + Data Structure) 자료형(Data Type) 내장 자료형 – 예: int x, float y, char z; 사용자 정의 자료형 – 예: Stack z; typedef 사용

2 알고리즘(Algorithm) 알고리즘(algorithm): 컴퓨터로 문제를 풀기 위한 일련의 단계적인 절차 알고리즘의 조건
입 력 : 0개 이상의 입력이 존재해야 한다. 출 력 : 1개 이상의 출력이 존재해야 한다. 명백성 : 각 명령어의 의미는 모호하지 않고 명확해야 한다. 유한성 : 한정된 개수의 단계 후에는 반드시 종료되어야 한다.  가장 중요함. 유효성 : 각 명령어들은 실행 가능한 연산이어야 한다.

3 알고리즘(Algorithm) … 프로그램 = 자료구조 + 알고리즘 (예) 최대값 탐색 프로그램 = 배열 + 순차탐색 자료구조
temp←score[0]; for i ← 1 to n-1 do if score[i]>temp then temp←score[i]; score[n] … 80 70 90 30

4 알고리즘(Algorithm) 영어나 한국어와 같은 자연어 흐름도(flow chart) 유사 코드(pseudo-code)
(예) 배열에서 최대값 찾기 알고리즘 1 2 3 4 5 6 7 8 9 10

5 알고리즘-자연어 표기 읽기가 쉽다. 자연어의 단어들을 명확하게 정의하지 않으면, 의미 전달이 모호해질 우려가 있다.
(예) 배열에서 최대값 찾기 알고리즘 ArrayMax(A,n) 배열 A의 첫번째 원소를 변수 tmp에 복사 배열 A의 다음 원소들을 차례대로 tmp와 비교하여, 더 크면 tmp로 복사 배열 A의 모든 원소를 비교한 다음, tmp를 반환

6 알고리즘-흐름도(Flowchart) 직관적이고 이해하기 쉬운 알고리즘 기술 방법
그러나 복잡한 알고리즘의 경우, 흐름도의 구조가 상당히 복잡해짐. temp←A[0] i←1 i < n A[i]>temp temp←A[i] temp no yes i++

7 알고리즘-유사코드(Pseudo-Code)
알고리즘의 고수준 기술 방법 자연어보다는 더 구조적인 표현 방법 프로그래밍 언어보다는 덜 구체적인 표현방법 알고리즘 기술에 가장 많이 사용 프로그램을 구현할 때의 여러 가지 세부적인 문제들을 감출 수 있다. 즉 알고리즘의 핵심적인 내용에만 집중할 수 있다. ArrayMax(A,n) temp ← A[0]; for i←1 to n-1 do if temp < A[i] then temp ← A[i]; return temp;

8 알고리즘-C 언어 알고리즘의 가장 정확한 기술이 가능
반면, 실제 구현시의 많은 구체적인 사항들이 알고리즘의 핵심적인 내용들의 이해를 방해할 수 있다. 적절한 indentation(들여쓰기)은 프로그램 이해에 도움이 된다. #define MAX_ELEMENTS 100 int score[MAX_ELEMENTS]; int find_max_score(int n) { int i, temp; temp=score[0]; for (i=1;i<n;i++){ if (score[i] > temp){ temp = score[i]; } return temp;

9 알고리즘의 성능분석 알고리즘의 성능 분석 기법 수행 시간 측정 알고리즘의 실제 수행 시간을 측정
프로그램으로 구현하는 것이 선행되어야 함! 동일한 하드웨어를 사용하여 여러 알고리즘을 비교해야 함 알고리즘의 복잡도 분석 직접 구현하지 않고서도 수행 시간을 분석하는 작업 알고리즘이 수행하는 연산의 횟수를 측정하여 비교 시간 복잡도 분석: 알고리즘의 수행 시간 분석 공간 복잡도 분석: 알고리즘의 수행시 필요로 하는 메모리 공간 분석

10 알고리즘의 성능-수행시간 측정 컴퓨터의 수행시간을 측정하는 방법으로, clock 함수가 사용된다.
clock_t clock(void); clock 함수는 호출된 시점의 시스템 시각을 CLOCKS_PER_SEC 단위로 반환 수행시간을 측정하는 프로그램 #include <stdio.h> #include <stdlib.h> #include <time.h> void main(void) {    clock_t start, finish;    double  duration;    start = clock();     // 수행시간을 측정하고자 하는 코드....     // ....    finish = clock();    duration = (double)(finish - start) / CLOCKS_PER_SEC;    printf(“수행시간은 %f 초입니다.\n", duration); }

11 알고리즘의 성능-복잡도 분석 시간 복잡도는 알고리즘을 구현하는 연산들이 몇 번이나 수행되는지를 숫자로 표시
산술 연산, 대입 연산, 비교 연산, 이동 연산의 기본적인 연산 알고리즘이 수행하는 연산의 개수를 계산하여 여러 개의 알고리즘을 비교. 연산의 수행횟수는 고정된 숫자가 아니라, 입력의 개수 n에 대한 함수->시간복잡도 함수라고 하며, T(n) 이라고 표기. 프로그램 A 프로그램 B 워드2005 워드2000 연산의 수 = 8 3n+2 연산의 수 =26 5n2 +6

12 알고리즘의 성능-복잡도 분석 n을 n번 더하는 문제: 각 알고리즘이 수행하는 연산의 개수를 세어 본다.
단 for 루프 제어 연산은 무시한다. 알고리즘 A 알고리즘 B 알고리즘 C sum ←n*n; sum ← 0; for i ← 1 to n do    sum ←sum + n; for i←1 to n do   for j←1 to n do      sum ←sum + 1; 알고리즘 A 알고리즘 B 알고리즘 C 대입연산 1    n + 1      n*n + 1      덧셈연산   n     n*n      곱셈연산 나눗셈연산 전체연산수 2   2n + 1      2n2 + 1   

13 알고리즘의 성능-복잡도 분석 연산의 횟수 알고리즘C 알고리즘B 알고리즘A 입력의 개수n

14 시간복잡도(Time Complexity)
코드를 분석해보면, 수행되는 연산의 횟수를 입력 자료 크기의 함수로 만들 수 있다. ArrayMax(A,n) temp ← A[0]; 1번의 대입 연산 for i←1 to n-1 do 루프 제어 연산은 제외 if temp < A[i] then n-1번의 비교 연산 temp ← A[i]; n-1번의 대입 연산(최대) return temp; 1번의 반환 연산 총 연산수= 2n(최대)

15 빅오 표기법 자료의 개수가 많은 경우에는 차수가 가장 큰 항이 가장 영향을 크게 미치고, 다른 항들은 상대적으로 무시할 수 있다. (예) n=1,000 일때, T(n)의 값은 1,001,001이고 이중에서 첫 번째 항의 값이 전체의 약 99%인 1,000,000이고 두 번째 항의 값이 1000으로 전체의 약 1%를 차지한다. 그러므로, 시간복잡도 함수에서는 가장 영향을 크게 미치는 항만을 고려하면 충분하다. 빅오표기법: 연산의 횟수를 대략적(점근적) 으로 표기. 2개의 함수 f(n)과 g(n)이 주어졌을 때, 모든 n≥n0에 대하여 |f(n)| ≤ c|g(n)|을 만족하는 2개의 상수 c와 n0가 존재하면 f(n)=O(g(n))이다. 빅오는 함수의 상한을 표시한다. (예) n≥1 이면 2n+1 <10n 이므로 2n+1 = O(n) n=1000인 경우 T(n)= n2 + n + 1 99% 1% 연산의 횟수 입력의 개수n

16 빅오 표기법 예제: f(n)= 5 이면, O(1) n0 = 1, c = 10 일때, n ≥ 1에 대하여 5 ≤ 101 이므로
f(n)= 2n + 1 이면, O(n) n0 = 1, c = 3 일때, n ≥ 1에 대하여 2n + 1 ≤ 3n 이므로 f(n)= 3n2 + 100 이면, O(n2) n0 = 100, c = 5 일때, n ≥ 100에 대하여 3n2 +100 ≤ 5n2 이므로 f(n)= 52n + 10n2 + 100이면, O(2n) n0 = 1000, c = 10 일때, n ≥ 1000에 대하여 52n + 10n2 + 100 ≤ 102n 이므로

17 빅오 표기법 O(1) : 상수형 O(logn) : 로그형 O(n) : 선형 O(nlogn) : 로그선형 O(n2) : 2차형
O(nk) : k차형 O(2n) : 지수형 O(n!) : Factorial형 시간복잡도 n 1 2 4 8 16 32 logn 3 5 nlogn 24 64 160 n2 256 1024 n3 512 4096 32768 2n 65536 n! 40326 26313×1033

18 최선, 평균, 최악의 경우 알고리즘의 수행시간은 입력되는 자료 집합의 특성에 따라 달라질 수 있다.
(예) 정렬 알고리즘의 수행 시간은 입력 자료 집합의 특성에 따라 다를 수 있다. 최선의 경우(best case): 수행시간이 가장 빠른 경우 (이미 정렬된 데이터) 평균의 경우(average case): 수행시간이 평균적인 경우 최악의 경우(worst case):수행시간이 가장 늦은 경우(역순으로 정렬된 데이터) 최악의 경우 최선의 경우 평균적인 경우 A B C D E F G 입력 집합 수행시간 100 50 최선의 경우: 의미가 없는 경우가 많다. 평균적인 경우: 계산하기가 상당히 어려움. 최악의 경우: 가장 널리 사용되며, 계산하기가 용이함.

19 최선, 평균, 최악의 경우 예: 순차탐색(Sequential Search)
최선의 경우: 찾고자 하는 숫자가 맨앞에 있는 경우 (5를 찾는 경우) ∴ O(1) 최악의 경우: 찾고자 하는 숫자가 맨뒤에 있는 경우 (43을 찾는 경우) ∴ O(n) 평균적인 경우: 각 요소들이 균등하게 탐색된다고 가정하면 (1+2+…+n)/n=(n+1)/2