- Running Time:
- 알고리즘: 입력 개체를 출력 개체로 전환시키는 일
- Running Time은 일반적으로 입력 크기(n)에 정비례한다.
- 컴퓨터 공학에서는 가장 오래 걸리는 경우(Worst Case)를 분석한다.
- 분석이 쉽다.
- 게임, 금융, 로봇 등의 분야에서 Worst Case가 매우 중요하다.
- 시행적 분석(Experimental Studies)
- 알고리즘을 직접 짜서 프로그램을 돌려 시간을 재는 함수등을 이용해 Running Time을 재는 방법
- 알고리즘을 직접 짜는 것이 중요하며, 개발자의 실력차에 따라 차이가 발생한다.
- 실험에 포함되지 않은 입력값이 존재할 수 있다.
- 두 알고리즘을 비교할 때, 동일한 하드웨어와 소프트웨어 사용이 필수적이다.
- 점근적 분석(Theoretical Analysis)
- 고급 서술로 실행하지 않고도 분석이 가능하다.
- 입력크기(n)에 대한 함수로 Running Time을 표현할 수 있다.
- 하드웨어와 소프트웨어 환경을 무시하고 분석할 수 있다.
- n이 충분히 커지는 경우를 대비한다.
- 의사코드(PseudoCode)
- 알고리즘을 서술하기 위한 고급 서술 방법
- 산문보다 구조적이다.
- 프로그램보다 대략적이며 세부적인 부분은 표현하지 않는다.
- 의사코드 사용법
- 제어문
- if_(condition)_then_(action)_[else_]
- while_(condition)_do_(action)_
- repeat_(action)_until_(condition)_
- for_(condition)_do_(action)
- 중괄호 대신 들여쓰기를 사용함
- 함수표현
- 제어문
Algorithm method (arg[,arg...])
Input ~
Output ~
-
-
-
- 표현
- <- 할당(C++에서의 =)
- = 동일(C++에서의 ==)
- 제곱과 같은 수학적 표기법 가능
- 표현
-
-
-
- 의사코드를 활용한 점근석 분석
- 알고리즘을 의사코드로 서술한다.
- Primitive Operation들의 수를 집계한다.
- 알고리즘의 Running Time을 Input size(n)에 관한 함수로 표현한다.
- 알고리즘 Running Time에 대한 함수를 Big-O표기법으로 표현한다.
- Random Access Machine (RAM)
- 무제한의 메모리를 가진 가상의 Cpu
- 이 가상의 기계는 메모리가 무한하며, 임의의 메모리셀에 넘버링이 되어있다.
- Primitive 연산 : 알고리즘에서 수행되는 연산중 기본 연산
- 의사코드를 보고 알 수 있음
- 프로그래밍 언어에서 구애 받지 않고 사용가능
- RAM 모델에서는 Input size(n)에 관계없이 일정한 수행시간(상수시간)이 걸린다
- 종류
- 사칙 연산
- 변수에 값 할당
- 배열에서 임의의 index에 접근
- 함수호출
- 함수의 return
- Primitive 연산 Count
- 의사코드 조사
- Primitive operation의 최대 개수 결정
- Input size(n)에 대한 함수로 결정
- 의사코드를 활용한 점근석 분석
Algorithm arrayMax(A,n) current <- A[0] 할당 한 번, 접근 한 번 -> 2 *for i <- 1 to n-1 do -> 3n if A[i] > currentMax then 인덱스에 접근 한 번 비교연산 한 번 n-1 반복 -> 2(n-1) currentMax = A[i] 인덱스에 접근 한 번, 할당 한 번 n-1반복 ->2(n-1) return currentMax 한 번 -> 1 -> 총 연산 수 : 7n-1 |
*
//i=1~n -> i=n이되어야 for문 탈출 -> i는 n까지 증가 -> 증가연산 n번
for (i=1 ;i<=n-1 ;i++)
// 1번 비교연산 n번 n-1번 증가
// n-1연산 n번
//연산 수는 3n
- Running Time 추정
알고리즘 arrayMax의 worst case일때 primitive operation 연산 수는 7n - 1
|
* a, b 는 컴퓨터의 하드웨어와 소프트웨어의 성능에 대해 영향을 받을 수 있다.
** 다만 n에관한 함수 T(n)에는 영향을 주지않는다. -> 차수가 바뀌진 않음
- n에관한 함수를 이용한 Running Time 추정
- n이 충분히 커지면 함수의 값 보다는 함수의 증가율이 유의미 (극한개념)
- 함수의 증가율로서 측정
- 최고 차항이 아닌 항은 함수의 증가율에 영향을 미치지 않음
- n이 충분히 커지면 계수는 증가율에 영향을 미치지 않는다
- 중요한 건 최고차항의 차수
- Big-Oh notation
- O(g(n)) : f(n) <= c*g(n) 을 만족하는 함수들의 집합
- (n>= n0, n0는 자연수), (c는 양의 실수, f(n),g(n)은 n에 대한 함수)
- "Big-Oh of g(n)" or "Oh of g(n)"
예시 -7n - 1 은 O(n) c = 7 , n0 = 1 -3n^3 + 20n^2 + 5 은 O(n^3) c = 4 ,n0 = 21 일반적으로 g(n),c,n0은 최솟값으로 표기 |
- Big-Oh 표기 법
- g(n)은 가장 낮은 차수로 표현
- g(n)은 계수가 1인 단항식으로 표현 (ex. n, n^2, n^3, log(n), 2^n)
- Big-Omega : 증가율이 작은 함수들의 집합 (증가율의 하한)
- Omega(g(n)) : f(n) >= c*g(n) 을 만족하는 함수들의 집합
- (n>= n0, n0는 자연수), (c는 양의 실수, f(n),g(n)은 n에 대한 함수)
- Bif-Theta : 증가율이 같은 함수들의 집합
- Theta(g(n)) : c'*g(n) <= f(n) <= c"*g(n) 을 만족하는 함수들의 집합
- (n>= n0, n0는 자연수), (c'과 c" 는 양의 실수, f(n),g(n)은 n에 대한 함수)
'DataStructure' 카테고리의 다른 글
[자료구조] Lists (0) | 2022.04.17 |
---|---|
[자료구조] Vector (0) | 2022.04.16 |
[자료구조] Queue (0) | 2022.04.09 |
[자료구조] Stacks (0) | 2022.04.08 |
[자료구조] Linked Lists (0) | 2022.04.08 |