선형/이진 탐색알고리즘 평가하기 및 주의사항

이 글은 코드잇의 알고리즘 강의와 오픈소스들을 참고하여 정리한 글입니다^^

선형탐색 알고리즘 평가하기

각 변수선언, 함수들을 한 줄씩 보면, 모두 리스트의 크기(n)과는 상관없이 일어나므로 O(1)이 소요된다.

while 반복문 또한, 한번 일어났다고 가정하면, n과 관계없으므로 반복횟수 X O(1)이 소요된다.

이 때, Best 경우 반복문 1번만에 = 첫 원소가 찾는 element인 경우,
걸리는 시간은 4 * O(1) = O(4) 역시 O(1)라 할 수 있다.

최악의 Worst 경우 반복문 n(0~n-1)번 돌아도 찾는 element가 리스트에 없는 경우로서,
걸리는 시간은 3*O(1) + O(1)*n이며, O(1) * n은 O(n)으로 나타낼 수 있다. ( 리스트의 개수만큼 반복된다. n이 관여)
즉, O(n +3)이 된다. 하지만, 점근표기법에서는 3은 없애줘도 되므로 O(n)이 된다.

이진탐색 알고리즘 평가하기

Best의 경우는 아래와 같이 반복문이 1번 도는 시간으로서, O(4) = O(1)이다.

하지만, 이진탐색의 Worst(리스트에 없는 경우) 는 반복문이 몇번 돌까?

loga(b) = x 와 log2(x) = y의 의미 :

    혹은 b를 a로 몇번 나누어야지 1이 되는가? 이다.
    컴퓨터 알고리즘 문제에서는 a가 2인 경우가 많다.
    log2(16)은 16을 2로 몇번 나누어야(몇번 반토막내야) 1이 나오는지 생각해보면, 4번이다.
    예를 들어, 길이가 16인 리스트가 있다면, 총 4번 반토막 내어야한다.

리스트의 원소길이 n 을 2로 몇번나누어야 1이 나오는지 횟수 = log2(n) 으로 나타낸다.
즉, lg(n) = n(리스트의 길이)를 몇번을 2로 나누면 1이 나오는지 = 몇번 반토막 내면 1이 나오는지라고 하였다.

그렇다면, 이진탐색의 Worst는 [ 반복문1회(O(1)) * lg(n) ] + O(3) = O(lg(n))이다.

정리하자면, 아래와 같다.

알고리즘에서는 보수적이라 최악의 경우를 자주 살핀다. 그러므로 아래와 같이 부른다.

1. 선형탐색 = Big-O of n 알고리즘
2. 이진탐색 = Big-O of lg(n)알고리즘

나의 정리

1. 알고리즘 최악의 경우는 element가 list에 없어서 반복문(회당 O(1))을 모두 돈 경우로서, n과 관련된다.
2. 선택탐색은 n번 / 이진탐색은 log2(n)번 반복문을 돈다. ( n은 리스트의 원소 개수)

알고리즘 평가시 주의사항

코드의 모든 줄은 O(1)인가요?

아닙니다!
인풋 크기와 상관 없이 실행되는 코드만 O(1)입니다. 그렇지 않은 코드는 시간 복잡도를 따져봐야 합니다.
예를 들어서 sorted 함수나 list.sort 메소드를 사용하면 내부적으로 O(nlgn)의 정렬이 이루어집니다.

만약 리스트에서 in 키워드를 통해 값의 존재 여부를 확인하면 내부적으로 O(n)의 선형 탐색이 이루어집니다.

파이썬의 내장된 정렬 알고리즘은 timsort라는 것입니다. 최악 or 평균의 경우 O(n lg n), 최고의 경우 O(n)이라고 하네요.
합병 정렬과 퀵 정렬도 평균 O(n lg n)입니다.