순차 탐색.

탐색 방법론.

그냥 처음부터 끝까지 하나하나 다 비교한다.

특징.

1. 느리지만 세부적인 방법론에 따라 빠를 수도 있다.

* 교수님이 말씀했던건데 네이버나 다음 등의 포털사이트에서 자주검색되는 질문등은 파일로 만든후 순차적으로 보여준다고 한다. 자주 검색될수록 앞에 갖다놓으면 더 빨라진다고 함.(맞는지는...)

2. 성공적인 탐색의 경우(최선) 1번의 비교로, 최악의 경우 N번의 비교가 필요하므로 평균적으로 N/2번의 비교가 필요하다. 최악의 경우에는 모든 원소를 비교해야 하므로 항상 N+1번의 비교가 필요하다.

5000개 돌리면 2.8초가 나온다.

# -*- encoding: cp949 -*-
import time
import random
import Queue
   
N = 5000

class Dict:
    class node:
        def __init():
            self.key = -1
    def __init__(self,max):
        self.a = [self.node() for i in range(max)]
        self.n = 0
    def search(self, search_key):
        i = 1
        while i<=self.n and self.a[i].key != search_key:
            i += 1
        if i==self.n+1: return -1
        else: return i
    def insert(self, v):
        self.n += 1
        self.a[self.n].key = v

def init(key, search_key):
    temp = [0 for i in range(N+1)]
    for i in range(1,N+1):
        key[i] = i
        search_key[i] = i
    for i in range(1,N+1):
        index = random.randint(1,65536)%N + 1
        if temp[index]==0:
            temp[index] = key[i]
        else:
            while temp[index] != 0:
                index = (index%N) + 1
            temp[index] = key[i]
    for i in range(1,N+1):
        key[i] = temp[i]

def main():
    d = Dict(N+1)
    key = [0 for i in range(N+1)]
    search_key = [0 for i in range(N+1)]
    init(key,search_key)
    for i in range(1,N+1):
        d.insert(key[i])
    start_time = time.time()
    for i in range(1,N+1):
        result = d.search(search_key[i])
        if result==-1 or key[result] != search_key[i]:
            print u'탐색 오류.'
    print u'순차 탐색의 실행 시간 (N = {} ): {}'.format(N,time.time()-start_time)
    print u'탐색 완료.'


if __name__=='__main__':
    main()