알고리즘 4주차 - 알고리즘 시간복잡도

Keywords : 순차 탐색, 이진 탐색, 버블 정렬

 

순차 탐색

• 원소들을 처음부터 찾아 비교하여 탐색
• O(n) 알고리즘, 선형 시간
• Not 효율적, but 효과적
• 선형 탐색 : 모든 원소들을 조사

 

이진 탐색

• 입력 받은 리스트에서 원하는 원소 있으면 인덱스, 없으면 null 반환
• 탐색 범위의 중간부터 시작해 비교를 통해 절반의 숫자 제거
• O(log2n) 알고리즘, 로그 시간
• 순차 탐색보다 빠르고 효율적임
• 단, 정렬이 되어 있어야 함

# 이진 탐색 알고리즘 구현
def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]

        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return None

my_list = [1, 3, 5, 7, 9]

print(binary_search(my_list, 3))
print(binary_search(my_list, -1))

 

정렬

• O(n^2) 알고리즘,
• 버블 정렬 : 이웃한 두 개의 원소를 비교하여 일일이 순서를 비교