배열 데이터를 보면 선형 탐색을 찾을 수 있습니다.


English           german

house

 haus

 car

 auto

 table

 tabelle


탐색하는 방법은 2가지 입니다.   키워드가 들어있는 배열을 찾아서 바로 번지를 구하는 것과

처음부터 배열을 훑어보다가  원하는 키워드가 있으면 번지를 알려주는 것입니다.


반환하는 방법 [ Recursive Solution ]

A - array ,low index , high index, key : key word


LinearSearch( A,low, high, key)


if  high < low :

    return NOT_FOUND


if   A[low] = key:

    return low

  

return LinearSearch(A, low + 1, high, key)


코드를 위와 같이 할 수 있습니다


아무튼 반환 관계중에 예를 들면 피보나치 수열이 있습니다.  0, 1, 1, 2, 3, 5, 8, 13 * *  *


더 설명하면  이렇습니다 .. 선형 탐색의 런타임 시스템을 살펴봐야 겠네요..




시스템을 n번 돌리면 정수값만 나옵니다..  

값이  고정입니다..  여기서 간단한 퀴즈


1. 배열에 원소가 존재할 때, 최상의 런타임 케이스는 무엇인가??    




2. 배열에 키워드가 없다면 선형탐색의 런타임 케이스 무엇인가???




반복하는 버전 [ iterative version ]

A - array ,low index , high index, key : key word


LinearSearch( A,low, high, key)


for i from low to high :

   if A[i] = key :

       return i


return NOT_FOUND


Summary


1) 반환하는 방법을 사용할 수 있습니다

2) 반복관계, T 에 대응하도록 정의합니다

3) T(n) 을 정의하는 것은 최악의 경우 런타임 입니다

4) 선택적으로 반복적인 솔루션을 만들수 있습니다.



저작자 표시
신고

'Study > 알고리즘' 카테고리의 다른 글

Binary Search with example  (0) 2016.11.19
Linear Search 1  (0) 2016.11.19
분할과 정복 알고리즘 도입  (0) 2016.11.19
피보나치 수열 값에서 마지막 숫자 구하기  (0) 2016.10.08
[week 1] Find Max Pairwise and multiply it  (0) 2016.09.19

WRITTEN BY
Profile
비타오백
Enjoy your stage!

받은 트랙백이 없고 , 댓글이 없습니다.
secret