빅오

• 이진검색과 선형검색을 통해 알고리즘의 효율성을 결정하는 주된 요인이 알고리즘 수행에 필요한 단계 수인 것을 알 수 있다.
  하지만 단순히 어떤 알고리즘을 10단계 알고리즘, 200단계 알고리즘이라고 표시할 수는 없다.
• 선형검색을 예로들면 배열의 수만큼 단계가 필요하므로 배열에 따라 단계 수가 다르다. 원소가 10개인 배열은 10단계가 필요하고 200개인 원소는 200단계가 필요하다.
• 이런 선형검색을 수치로 메기는 법보다 정확한 방법은 배열 N개의 원소가 있을 때 선형검색에 N단계가 필요하다고 표현하는 것이다. 하지만 이런 표현은 좀 장황하다.
• 컴퓨터 과학자들이 서로 간에 시간 복잡도를 쉽게 소통할 목적으로 자료구조와 알고리즘의 효율성을 간결하고 일관된 언어로 설명하기 위해 수학적 개념을 사용했다. 이러한 표현을 빅 오 표기법 이라고 한다.

O(1)

• 데이터 크기에 상관없이 알고리즘에 필요한 단계 수가 일정하다는 의미이다.

def print_first(my_list):
    print(my_list[0]) 

print_first([2, 3])
print_first([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53])

• print_first를 처음 출력할 때는 요소가 2개를 넘겨줬고, 두번째 출력할 때는 16개를 넘겨줬다. 두 경우 걸리는 시간의 차이는 거의 없다. 어차피 맨앞 요소를 받아오기 때문에 리스트의 길이는 상관이 없다.

O(N)

• 배열 내에 N개의 원소가 있을 때 알고리즘을 끝내는데 N개의 단계가 필요함을 표현하는 방법이다.

def print_each(my_list):
    for i in range(len(my_list)):
        print(my_list[i])

• 반복문이 있고, 반복되는 횟수가 인풋의 크기와 비례하면 일반적으로 O(N)에 해당한다.

O(log N)

• 이진검색이 선형검색보다 빠름을 알 수 있다. 빅 오 표기법 관점에서 데이터가 커질수록 단계 수가 늘어나니깐 O(1)에 속하지도 않고 원소 수보다 단계 수가 휠씬 적어 O(N)에도 속하지 않는다.
• 100개의 원소가 있으면 7단계만 걸린다. O(1)과 O(N) 사이인 O(log N)에 속한다.
• O(log N)은 데이터가 두 배로 증가할 때마다 한 단계씩 늘어나는 알고리즘을 설명하는 방법이다.

def print_powers_of_two(n):
    i = 1
    while i < n:
        print(i)
        i = i * 2

• n이 128 이면 2, 4, 8, 16, 32, 64까지 총 7번 실행된다.
• 그래프로 살펴보면 다음과 같다.