탐색 알고리즘, 시간복잡도 파이썬

선형 탐색법

def findIndexLinear(array, condition):
  for i in range(len(array)):
      if array[i] == condition:
          return i

# 최선의 경우 - 한번의 탐색으로 해결
findIndexLinear([2,4,5,1,6], 2)
# 최악의 경우 - 배열의 크기만큼 탐색으로 해결
print(findIndexLinear([2,4,5,1,6], 6))

시간복잡도 = O(n)

** 데이터 수가 많아지면 효율이 굉장히 안좋아짐

정렬되지 않은 데이터에 자주 사용

 

이진 탐색법

def findIndexBinary(array, target):
    start = 0
    end = len(array)-1
    mid = (start+end)//2
    
    while end - start >= 0:
        if array[mid] == target:
            return 1
        elif array[mid] <= target:
            start = mid + 1
        else:
            end = mid - 1
        mid = (start+end)//2
    return -1
    # 찾는 결과가 없을 때, -1을 리턴
    
   print(findIndexBinary([1, 2, 5, 3, 6], 5))

시간복잡도 = O(logN)

** 선형 탐색법과 비교하면 더 빠르다. (상황에 따라서는 선형이 더 빠를수도 있음 - 요소가 앞에있을 경우)

평균적으로 빠를 뿐, 항상 빠른것은 아님.

정렬된 데이터에 자주 사용

 

해시 탐색법

arrayA = [12,25,36,20,30,8,42]
# 앞에서 배운 2개의 검색 알고리즘(선형 탐색, 이진 탐색)은
# 배열의 요소를 데이터 수만큼 준비하면 충분했지만,
# 해시 탐색법은 이와 달리 저장하는 데이터의 1.5~2배를 준비해야 합니다.
arrayB = [0] * 11

# 저장할 요소의 배열을 순회하면서
for i in range(len(arrayA)):
    #저장할 공간(첨자)를 계산
    temp = arrayA[i] % 11;
    # 저장할 공간에 데이터가 있으면
    if arrayB[temp] != 0:
        # 데이터가 없는 공간을 찾을때까지
        while arrayB[temp] != 0:
            # temp를 증가, 하지만 배열의 크기가 11이므로, 
            # 인덱스가 10을 넘으면(배열의 크기를 넘으면 안되기에) 0으로 변경합니다.
            print(temp)
            if temp < len(arrayB)-1:
                temp += 1
            else:
                temp = 0
            print(temp)
        # 데이터가 없는 공간을 찾으면 저장합니다.
        arrayB[temp] = arrayA[i]
    # 저장할 공간에 데이터가 없으면
    else:
        # 데이터가 없는 공간을 찾으면 저장합니다.
        arrayB[temp] = arrayA[i]
print(arrayB)

# 저장한 데이터와 찾을 요소를 Argument로 넣어줍니다.
def findHashData(array, target):
    # 저장할 공간에 데이터가 있어서 +1해준 경우를 제외하고는
    # 첨자 = 저장할데이터 % 저장할 배열의 크기입니다..
    uniqueValue = target % len(array);
    
    # 찾고자 하는 값이 맞을 경우가 나올때까지
    while array[uniqueValue] != target:
        # 결과가 원하는 값이 아니면, (저장할데이터+1) % 저장할 배열의 크기
        uniqueValue = (uniqueValue+1) % len(array)
    return uniqueValue

print(findHashData(arrayB, 42))
# => '저장 위치는 0번째 요소입니다.'

시간복잡도 = O(1) * 해시 충돌이 일어날경우 O(n)

기존의 탐색보다 어렵지만, 검색속도는 빠르다.

파이썬에는 이미 딕셔너리로 해시를 구현 한 상태이다.