[학교-알고리즘] 알고리즘과 순차검색 이진검색 피보나치 슈도코드

알고리즘 : 효율, 분석 그리고 순서

• 효율적인 개념의 알고리즘 소개

ex) 크기 n인 배열 S에서 x 라는 숫자가 있나?

S [10, 7, 11, 5, 13, 8]   x = 11

사람은 한번에 11이 있다는걸 찾을 수 있지만 이것을 컴퓨터에게 어떻게 명령할 것인가?

step-by-step으로 문제를 해결해야한다.

순차검색

• input : int n ( >0), S [1...n], x
• output : location of x, if x is in S
                0                 , if x isn't in S

슈도 코드

이진 검색

• 가정 : 입력 배열 S[] 는 non-decreasing 이다. ( increasing 이라 표기하지 않는 이유는 increasing은 1,2,3,4,4 처럼 같은 값이 있을때를 포함하지 않는다)

슈도코드

피보나치 수열

T(n) :  재귀적 피보나치 트리의 전체 수

T(n) : , 시간 복잡도는 2^n 

재귀적 피보나치는 비효율적!

재귀적 피보나치 슈도코드

반복적 피보나치 슈도코드

알고리즘 분석

2가지의 복잡도 파라미터

1. 입력 크기
   
1.  배열의 크기 ex) 10개의 숫자 배열에서 10 찾기
2.  단일 숫자 ex) 6th 피보나치 
3.  그래프에서의 간선과 정점의 크기
   
   
2. 기본 연산
   

시간 복잡도 분석

어떤한 입력 크기에서 얼마나 많은 정도의 기본 연산이 이루어졌는가

ex) 최악의 경우, n 개 크기의 배열에서 순차 검색시 n 번 모두 비교한다. ( 찾는 값이 맨 끝, n 에 있는 경우)

시간 복잡도 분석의 유형

1. Every case analysis : 모든 n 개의 입력에 대해 같은 횟수의 비교를 갖는 경우
2. Non-Every case analysis 
1. Best case
2. Worst case
3. Average case

순차 검색의 복잡도 분석

1. 입력 크기 : n( 배열의 크기)
2. 기본 연산 : 현재 위치의 아이템과 찾으려는 아이템을 비교하는 연산

1. Best case : 1 ( 1번째가 찾으려는 값)
2. Worst case : n ( 맨 마지막이 찾으려는 값)
3. Average case : 계산해야함!