[알고리즘]시간복잡도 Big O

시간복잡도 란?

1. 기본개념

한마디 버전이 길지만, 복잡한 내용은 아닙니다.
아래를 봅시다.

l = [1, 2, 3]

for n in l:
    print(n)

위 함수에서 리스트 l 에 들어있는 데이터가 3개니까 3번 돌아갑니다. 여기서 리스트 안에 있는 갯수를 n 이라고 하고 n이 커질 수록 알고리즘이 행하는 액션의 횟수가 늘어납니다. 만약 데이터가 5개면 5번 돌아 갈것이고, 20,000개만 20,000번 돌아가게되겠지요? 그래서 위 알고리즘의 시간복잡도는 O(n) 입니다. n의 갯수에 따라 복잡해 진다. 라는 이야기지요.

2. 시간 복잡도 표

물론 이것 말고도 더 많습니다. 다항 시간, 분수지수, 이중 지수 시간 등이 더 있지만, 우리는 기본적으로 위에 시간 복잡도만을 대체적으로 다루고 면접등에서 질문을 받습니다. 조금 더 고차원적인 알고리즘을 만드시는 현업에 계신 분들께서는... 파이팅! ㅜㅜ

왼쪽 그래프를 보시면 시간 복잡도에 상관되어 인풋의 크기에 따라 얼마나 많은 시간이 걸릴지를 예상할 수 있는 표가 있습니다.(출처: 위키피디아)

제가 외국회사에서 면접을 볼때 시간복잡도를 이해 하는 것보다 더 많이 찾아본 것은.. '아니.. 영어로는 어찌 말하지..?' 였습니다. 그래서 아래 표도 준비해 봤습니다.

3. 상수 시간 예제

l = [1, 2, 3]

print(l[2])


>>>3

위와 같이 전혀 인풋의 갯수와 상관이 없는 상황일 경우에 사용합니다.

4. 로그 시간 예제

l = [1, 2, 3, 5, 8, 22, 34, 55]
for index in range(0, len(l), 3):
    print(l[index])


>>>1
>>>5
>>>34

알고리즘은 각 단계에서 입력 데이터의 크기를 줄일 때 로그 시간 복잡성을 갖는다고 한다(입력 데이터의 모든 값을 볼 필요는 없다).

5. 선형 시간 예제

l = [1, 2, 3]

for n in l:
    print(n)

알고리즘은 실행 시간이 입력 데이터의 크기와 거의 선형적으로 증가할 때 선형 시간 복잡성을 갖는다고 한다. 이것은 알고리즘이 입력 데이터의 모든 값을 검사해야 할 때 가능한 가장 좋은 시간 복잡성이다.

6. 선형 로그 시간

def merge_sort(data):
    if len(data) <= 1:
        return

    mid, right = len(data) // 2
    left, right = data[:mid], data[mid:]
    
    merge_sort(left)
    merge_sort(right)

    l, r, d = 0, 0, 0

    while l < len(left) and r < len(right):
        if left[l] < right[r]:
            data[d] = left[l]
            l += 1
        else:
            data[d] = right[r]
            r += 1
        d += 1

    if l < len(left):
        del data[d:]
        data += left[l:]
    elif r < len(right):
        del data[d:]
        data += right[r:]


>>> [1, 23, 41, 55, 223, 452, 666]

위는 머지정렬의 파이썬 예시 입니다. 시간복잡도는 O(n log n) 입니다. 추후 '정렬계의 명예의 전당' 이라는 글을 쓸텐데, 여기서 간단하게 알려드리자면, 머지소트는 리스트를 반으로 쪼개고 다시 쪼개고 해서 작게만들어 다시 작은 수 부터 정렬하는 기법입니다. 쪼개면서 log n 의 시간이 소요되고, 다시 붙이면서 n 의 시간이 소요됩니다.

머지소트 개념:

머지정렬의 개념도 입니다(출처: 위키피디아)

7. 2차 시간, 3차 시간

def bubble_sort(l):
    swap = True
    while swap:
        swap = False
        for i in range(len(l)-1):
            if l[i] > l[i+1]:
                l[i], l[i+1] = l[i+1], l[i]
                swap = True

lst = [41, 452, 223, 1, 23, 55, 666]
bubble_sort(lst)
print(lst)


>>> [1, 23, 41, 55, 223, 452, 666]

위는 버블 소트의 예제입니다.

알고리즘은 입력 데이터의 각 값에 대해 선형 시간 연산을 수행해야 할 때 2차 시간 복잡성을 갖습니다.
쉽게 말해 2중 루프로 돌아가는 알고리즘입니다.(3번돌아가면, 3차 시간) n log n도 2번 돌아가지만, 그 중 하나가 log n 의 시간 복잡도를 가지는 것입니다. 상수로 시간복잡도를 늘리거나 줄이는 것은 시간 복잡도 개념에서 무시합니다. 아래 따로 설명하겠습니다~!

8. 지수 시간

def recursive_fibonacci(n):
   if n <= 1:
       return n
   else:
       return(recursive_fibonacci(n-1) + recursive_fibonacci(n-2))

steps = 10

# 양수만
if steps <= 0:
   print("음수 노노")
else:
   print("직전 숫자와 그 전 숫자의 합이 현재 숫자:")
   for i in range(steps):
       print(recursive_fibonacci(i))


>>> 직전 숫자와 그 전 숫자의 합이 현재 숫자:
>>> 0
>>> 1
>>> 1
>>> 2
>>> 3
>>> 5
>>> 8
>>> 13
>>> 21
>>> 34

위는 재귀 피보나치 예제입니다. 이 알고리즘은 입력 데이터 세트에 추가될 때마다 시간이 두 배로 늘어나는 지수적인 시간 복잡성을 갖습니다. 이런 종류의 시간 복잡성은 보통 Brute-Force 알고리즘에서 볼 수 있습니다.

피보나치 개념도:

피보나치 재귀 트리 개념도(출처: 비주얼고 - https://visualgo.net/bn/recursion)

9. 팩토리얼 시간

from math import factorial

print(factorial(1))
print(factorial(3))
print(factorial(5))
print(factorial(7))
print(factorial(9))


>>> 1
>>> 6
>>> 120
>>> 5040
>>> 362880

파이썬에는 math 모듈에 factorial 함수가 있습니다. 2씩 늘어났지만, 결과는 기하 급수적으로 늘어난 것을 볼 수 있습니다. 지수 시간과 팩토리얼 시간은 이렇게 기하 급수적으로 늘어나는 것을 이용하여 암호화 알고리즘에 사용됩니다. 무작위 대입 공격에 어마어마한 시간과 비용을 들게 만드는 방식입니다.

10. 치트키!

인생은 이미 복잡합니다. 복잡한 내용을 일일히 찾아 다니시지 않게 치트키를 함께 올립니다.

출처 (Big O Cheatsheet http://bigocheatsheet.com/)

정렬계의 명예의 전당(출처 : Big O Cheatsheet http://bigocheatsheet.com/)

Big O 말고도 다른 것들이 있습니다. 점근 표기법 인데요(asymptotic notation)

• 대문자 O 표기법
• 소문자 o 표기법
• 대문자 오메가(Ω) 표기법
• 소문자 오메가(ω) 표기법
• 대문자 세타(Θ) 표기법

압도적으로 Big O 표기법을 많이 사용합니다.

11. 주의 해야 할 점

시간복잡도를 계산하는데 있어서는 주의할 점이 있습니다. 

우리는 O(n/2) 이라 표기 하지 않습니다. n을 2로 나눈만큼만 시간이 필요하지만, 저런 상수는 n이 무한대로 늘어나면 큰 의미가 없습니다. 그래서 O(n+100) 이나 O(n*3)이라 O(n/2) 나 전부 우리는 O(n)으로 표기합니다.

>> 연습문제 15종 풀어보기(딩그르르 다른 포스트)