알고리즘의 분석(analysis) 공간적 효율성(Space Efficiency)과 시간적 효율성(Time Efficiency)

Slides:



Advertisements
Similar presentations
YES C 제 1 장 C 언어의 개요 1/34 제 1 장 C 언어의 개요 문봉근. YES C 제 1 장 C 언어의 개요 2/34 제 1 장 C 언어의 개요 1.1 프로그램과 C 언어의 특징 1.2 C 언어의 프로그램 구성 1.3 비주얼 C++ 통합 환경 들어가기.
Advertisements

Ch.4 수요관리와 수요예측 Ch.2 수요예측생산 ∙ 운영관리 1. 제 1 절 수요관리의 개념과 중요성 1. 수요관리의 필요성 정확한 수요예측은 사업의 성과를 좌우하는 매우 중요한 과제이다. – 수요는 판매량과 다르다. – 하지만 온갖 불확실성 요소가 난무하는 사업환경에서.
제6장 조건문.
프로그래밍1 및 실습 (C언어) - 3장 기본자료형 (3.6부터 끝까지) -
CHAP 1:자료구조와 알고리즘.
제 1장 C 언어의 소개.
제1장 소프트웨어 프로젝트 개요 1.1 프로젝트개요 1.2 프로젝트 유형 1.3 프로젝트 관리의 중요성과 실패 원인
CHAP 1:자료구조와 알고리즘 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
[사내 교육용 限, 대 고객자료로 절대 사용 不可]
시스템 생명 주기(System Life Cycle)(1/2)
알고리즘(Algorithm)  알고리즘 개요 (효율, 분석, 차수) Part 1 강원대학교 컴퓨터과학전공 문양세.
제7장 제어구조 I – 식과 문장.
알고리즘 강의 슬라이드 2 분할정복 강의 슬라이드 #2
4장: 자료형과 수식.
시스템 생명 주기(System Life Cycle)(1/2)
쉽게 배우는 알고리즘 5장. 검색트리
DSP와 TMS320F28X의 이해
EPS Based Motion Recognition algorithm Comparison
자료구조 김현성.
Dynamic Programming.
Ch. 10 Algorithm Efficiency & Sorting
Data structures 01.2: C++ classes 동의대학교 멀티미디어공학과 이광의교수.
제7장 손익분기점분석 1. 들어가기 학습목표 - 손익분기점의 개념을 이해할 수 있다. - 영업레버리지와 BEP분석의 관계를 알 수 있다. - 손익분기점을 산출하는 방법을 습득할 수 있다. 학습내용 - 손익분기점의 의의 - 영업레버리지 분석으로서의 BEP분석 - BEP 측정공식.
재귀 혹은 귀납 Recursive or Inductive Definition 집합을 정의하는 방법
CHAP 1:자료구조와 알고리즘 C로 쉽게 풀어쓴 자료구조 생능출판사 Slide 1 (of 28)
12 검색.
- 나는 내 마음의 주인공 – 집단상담프로그램 인제대학교 교육대학원 상담심리전공 하 정 선
4장 제어문 선택문: if 문, if – else 문, switch 문
컴퓨터의 기초 제 2강 - 변수와 자료형 , 연산자 2006년 3월 27일.
제 1 장 알고리즘 : 효율, 분석, 그리고 차수.
다음 주 과제 3장 읽어오기 숙제 해서 제출하기. 자료구조와 알고리즘, 순환 E304호,
Ch.02 Divide and Conquer (분할정복)
제1장 자료구조를 배우기 위한 준비.
알고리즘(Algorithm)  알고리즘 개요 (효율, 분석, 차수) Part 년 봄학기
Chapter 01 자료 구조와 알고리즘.
Chap. 1 Data Structure & Algorithms
[CPA340] Algorithms and Practice Youn-Hee Han
Dynamic Programming.
3장. 변수와 연산자. 3장. 변수와 연산자 3-1 연산자, 덧셈 연산자 연산자란 무엇인가? 연산을 요구할 때 사용되는 기호 ex : +, -, *, / 3-1 연산자, 덧셈 연산자 연산자란 무엇인가? 연산을 요구할 때 사용되는 기호 ex : +, -, *, /
Exponential and Logarithmic functions
제 1 장. 자료구조와 알고리즘.
Chapter 02. 소프트웨어와 자료구조.
제2장 통신 신호 및 시스템 해석(2).
C언어 응용 제 15 주 검색.
동적계획법과 최적화 문제 Dynamic Programming을 사용한 최적화 문제를 해결하는 알고리즘 설계 절차
CHAP 12:탐색 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
CHAP 12 : 탐색 C로 쉽게 풀어쓴 자료구조 생능출판사 2011.
알고리즘의 분석(analysis) 공간적 효율성(Space Efficiency)과 시간적 효율성(Time Efficiency)
합병정렬(Merge Sort) (1/2) 문제: n개의 정수를 (비내림차순으로) 정렬하시오.
CHAP 1:자료구조와 알고리즘.
알고리즘(Algorithm)  알고리즘 개요 (효율, 분석, 차수) Part 년 봄학기
Internet Computing KUT Youn-Hee Han
기술 진화와 진보.
쉽게 풀어쓴 C언어 Express 제6장 조건문 C Express Slide 1 (of 28)
제 8 장 계산복잡도 개론 검색 문제 알고리즘 강의 슬라이드 8 검색 문제
원가(C)-조업도(V)-이익(P) 분석
알고리즘 강의 슬라이드 2 분할정복 제 2 장 분할정복 도경구역, 알고리즘, 사이텍미디어, 1999.
쉽게 풀어쓴 C언어 Express 제6장 조건문 C Express.
강의 #11 탐색(Search).
알고리즘(Algorithm) – Divide and Conquer (분할정복)
알기쉽게 해설한 데이터구조 고 갑 승 한남대학교
9장. C 언어의 핵심! 함수. 9장. C 언어의 핵심! 함수 9-1 함수의 정의와 선언 main 함수 다시 보기 : 함수의 기본 형태 { } 그림 9-1.
어서와 C언어는 처음이지 제16장.
DataScience Lab. 박사과정 김희찬 (화)
조 병 규 Software Quality Lab. 한 국 교 통 대 학 교
동 행 코 칭 결 과 방문 상황 BEST WORST 김형* PRO 총평 목 / 디지털 평촌 센터
알고리즘 강의 슬라이드 7 정렬문제 알고리즘 해석 강의 슬라이드 #7
알고리즘의 분석(analysis) 공간적 효율성(Space Efficiency)과 시간적 효율성(Time Efficiency)
Chapter 7: Deadlocks.
Report #3- 문제 1 Set(집합) 추상 데이터 타입을 정의하고, 다음과 같은 연산자들을 포함시켜라. 여기서 S, S1, S2는 집합을 나타내고, i는 집합 원소를 나타낸다. 연산 의미 create() Return {} insert(S, i) If i є S then.
Presentation transcript:

알고리즘의 분석(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)  

[알고리즘 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