[알고리즘] 2주차 내용 초압축

알고리즘이란

주어진  input으로부터 output을 출력하는 명령어의 집합

 

매개변수: 입력값

인스턴스: 매개변수에 값을 할당한 사례

 

알고리즘은 모든 사례를 효율적으로 해결할 수 있어야한다.

input이 큰 경우에 비효율적으로 작동한다면 쓸모없는 알고리즘..! ㅠㅠ

 

알고리즘의 기술방법3

1. 자연어: 영어,한글

2. 프로그래밍 언어: C,Python

3. 의사코드(Pseudo-Code)

 

의사코드의 특징

배열을 사용할 수 있음

배열 사이즈 가변

수학적으로 표현

임의 자료형 사용 (number,bool)

추상적 명령

 

순차탐색 <- pre15p~

sort list 사용

best case: 비교 1번

worst case: 비교 N번

 

이진탐색

sort list 사용

best case: 비교 1번

worst case: 

 

=>

배열의 크기가 커질수록, 알고리즘 비교횟수가 더 크게 차이난다.

배열의 크기 128, 순차탐색의 비교횟수=128, 이진탐색의 비교횟수=8

 

# 피보나치 수열의 해결방법

1. 재귀함수 사용

T(n)=T(n-1)+T(n-2)+1=2^(2/n)*T(0) -> 지수함수로 증가하는 꼴, 비효율적이다

 

2.반복문 사용

새로운 배열을 생성해 원소값을 저장한다 (동적배열사용,Dynamic Programming)

T(n)=1+1+(n-1)=n+1 <- 여기서 +1 은 f[0],f[1]를 초기화한 계산을 의미한다.

 

=> 재귀함수는 f(n-1)항 계산을 위해 함수를 재귀적으로 수없이 호출해야하지만, 반복문은 배열에 값을 저장한 후 꺼내오면 되므로 시간복잡도가 훨씬 덜하다.

 

 

# 알고리즘 분석방법

 

좋은 알고리즘은 시간,공간 효율성에 의해 결정된다.

시간효율성: 얼마나 빠르게 계산하는지

공간효율성: 메모리를 얼마나 적게 사용하는지

 

절대적 시간 측정의 문제점

1. 알고리즘이 완전히 구현되어야함

2. 동일한 조건에서 언제나 일치해야함 <- 환경차이가 발생해서는 안됨

3. sw 환경이나 언어에 영향받으면안됨

4. 모든 input에 대해 적용되어야함

-> 절대적인 시간측정보다, 이론적 복잡도를 분석해서 알고리즘의 우열을 가려야함!

 

이론적 복잡도의 고려 사항 4

1. input size: 입력크기를 무엇으로 정의할지

- 복잡도 함수를 결정하는 요소

- 예시) 리스트 조회-리스트에 들어있는 값의 수, 다항식 연산-다항식의 차수 or 항의 개수 등등..,

2. basic operation: 어떤 연산이 가장 복잡도에 큰 영향을 미치는지

- 복잡도를 결정하는 핵심 연산(=가장 빈번하게 실행되는 연산)

3. 확장성: 입력크기 증가에 따라 처리시간이 어떻게 변화하는지

4. 입력데이터 특정: 입력값의 성질이 알고리즘 효율에 어떤 영향을 주는지

 

복잡도 함수T(n)

- input size(n)과 관련있음.

- 이때, n이 작을때는 알고리즘별 차이가 크지 않으므로, n이 충분히 클때를 고려해서 알고리즘을 분석해야함.

- n이 무한대로 도달할때, 점진적 성장률을 설명함.

 

시간복잡도 분석 종류4

- input size에 따라 기본연산이 얼마나 실행되는지 결정

- CPU, OS, 언어에 독립적이여야함.

1. ECA: 모든 가능한 input과 동작을 고려해서 분석

예시)

sum()

- 배열의 요소 수와 상관없이, 연산횟수가 일정하다면 T(n)=n이다.

- 기본연산: for문 + 값 할당문

교환정렬(exchange Sort)

- 교환정렬 개념: S[0]이 S[2...n-1]과 비교, S[0]이 S[n]보다 크면 서로 교환 ~~이걸 S[n-2]까지 반복한다.

- 기본연산: S[i] S[j] 요소 비교문

- T(n)=(n-1)+(n-2)+ ... +1 = (n-1)n/2

 

2. WCA: 최악의 경우 분석,  최악의 input에서 max time이 어떻게 되는지

예시)

순차탐색(Sequential search)

- 순차탐색 개념: S[0]부터 S[n-1]까지 순회하며 원하는 값(x)를 찾는다.

- 기본연산: S[n] !=x

- worst case: x가 마지막 요소이거나 존재하지 않을때

- W(n)=n

- 순차탐색은 x를 찾으면 종료하므로, input에 따라 연산횟수가 달라져 ECA를 할 수 없다. (best case:1 , worst case:n, avrage case: n/2)

 

3. ACA: 평균 분석, 모든 input이 동일한 확률일때의 시간 예측 (확률을 사용한다)

- 기본연산: S[n] !=x

예시)

순차탐색(Sequential search)

case1) x가 배열S에 존재하는게 보장된 경우

- x가 S[n]배열의 k번째 요소로 존재할 확률=1/n

- 연산횟수=k

=> A(n)=(n+1)/2 (k가 1~n일때를 모두 구해, 1/n을 곱함)

case2) x가 배열S에 존재하는게 보장되지 않은 경우

- x가 S[n]배열에 존재할 확률=p <- p값이 작아질수록, 시간 복잡도가 커진다!

- x가 S[n]배열에 존재하지 않을 확률=1-p

- x가 S[n]배열의 k번째 요소로 존재할 확률=p/n

=> A(n)=(배열에 있을 경우)+(배열에 없을 경우)=n(1-p/2)+p/2

 

4. BCA: 최선의 경우 분석. input이 이미 최적일때의 min time이 어떻게 되는지

- 기본연산: S[n] !=x

예시)

순차탐색(Sequential search)

- x가 첫번째 요소일때 base case가 되므로, B(n)=1

 

공간복잡도 분석

- 알고리즘이 얼마나 메모리를 효율적으로 사용하는지

- 대부분은 시간복잡도를 중요하게 생각하지만, 공간복잡도 또한 중요하다

 

QUIZ 어떤 분석 종류를 사용해야할까?

Q. 원자력 발전소에서 일하는 나

A. WCA. 핵터지면 안되니까...

 

Q. 인터넷 쇼핑몰을 운영하는 나

A. ACA. 일반 사용자 경험이 중요하므로

 

Q. 머가 제일 쓸모없을까요~?

A. ECA

 

Q. 머가 제일 분석하기 어려울까요~?

A. ACA. 모든 확률을 계산해야하므로

 

분석의 효율성 vs 분석의 정확성 -> 정확성이 먼저다

- 그리고 우리는 수학적증명을통해 정확성을 증명해야함!

- 정확하지않은 알고리즘이란? 무한 loop에 빠지는 알고리즘, output이 이상한 알고리즘