시간복잡도에 대해서 알아보자!

시간 복잡도(time complexity)란?

알고리즘이 문제를 해결하는 데 걸리는 시간

알고리즘의 성능을 나타내는 지표

코딩테스트 문제에서 항상 등장하는 알고리즘이 실행되는 제한 시간과 관련이 있다.

 

 

시간 복잡도 표현

일반적으로 시간 복잡도는 점근 표기법을 이용하여 나타낸다.

1. Big-Ω (빅 오메가) 표기법 / Ω(N) : 최선의 상황을 가정하는 표기법
2. Big-O (빅 오) 표기법 / O(N) : 최악의 상황을 가정하는 표기법
3. Big-θ (빅 세타) 표기법 / θ(N) : 평균의 상황을 가정하는 표기

가장 많이 쓰는 방법은 Big-O 표기법이다. Big-O 표기법은 최악의 경우 어느정도 속도가 나올 수 있는지 판단하여 로직 수정 / 속도 개선을 위한 하드웨어 교체 등에 도움을 준다. 친구와 약속에 늦을 경우, "나 제일 덜 늦으면(?) 5분 늦어!" 라던가,  "나 보통 늦으면 10분 정도 더 걸려"라고 말하지 않고, "정말 늦더라도 적어도 nn시까지는 도착해"라고 알려주는 것이 좋다는 것을 떠올려하면 Big-O가 많이 쓰이는 이유를 이해하기 쉽다!

 

 

Big-O 표기법

 

 

O(1) 상수시간

입력 데이터의 크기에 상관없이 일정한 시간이 걸린다.

# 단순 출력문
def print_hello(n):
  print("Hello World!")

# 1부터 n까지의 합 구하기
# n으로 어떤 숫자가 들어와도, 100억이 들어와도 단 한 번의 연산
def sum_from_1_to_n(n):
  return (n+(n+1))//2
  
# 리스트 값 접근
li = [1, 2, 3, 4, 5]
def get_item_of_list(n):
  return li[n]

 

 

O(n) 선형 시간

입력 크기(n)가  증가함에 따라 실행 시간이 같은 비율로 증가한다.

# 반복문을 사용한 1부터 n까지의 합
def sum_from_1_to_n(n):
  val = 0
  for i in range(1, n+1):
    val += i
  return val
  
'''
2n까지의 합을 구한다 하더라도, 
n이 커질수록 계수인 2가 사실상 큰 영향을 끼치지 못하기 때문에 
O(2n)이 아닌 O(n)
'''

 

 

O(log n) 로그 시간

입력 크기(n)가 두 배로 증가하더라도 실행 시간이 상수 시간만큼만 증가한다

ex) 이진 탐색 알고리즘 : 원하는 값을 탐색할 때, 매 단계마다 절반의 데이터만을 남긴다.

def binary_search(n):
  li = [-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5]
  l, r = 0, 10
  while l <= r:
    m = (l+r)//2
    if li[m] > n:
      r = m - 1
    elif li[m] < n:
      l = m + 1
    else:
      return m
  return -1

 

 

O(n log n) 선형 로그 시간

입력 크기(n)이 증가함에 따라 실행 시간이 n log n만큼 증가한다.

ex) 퀵 정렬, 병합 정렬, 힙 정렬

'''
<병합 정렬>

1. 분할(Divide): 입력 배열을 두 개의 동일한 크기의 하위 배열로 분할
                 매 단계마다 데이터의 크기가 절반으로 줄어들기 때문에 로그 시간에 비례하여 증가
2. 정복(Conquer): 하위 배열을 재귀적으로 정렬
                  각 하위 배열에 대해 실행되므로, 전체적으로 입력 배열의 모든 원소를 한 번씩 처리
                  즉, 선형 시간에 비례하여 증가
3. 결합(Combine): 정렬된 두 개의 하위 배열을 병합하여 하나의 정렬된 배열을 만듦
               입력 배열의 모든 원소를 한 번씩 처리하므로, 선형 시간에 비례하여 증가
               
=> 병합 정렬의 시간 복잡도 = 분할 단계의 O(log n) * 정복 및 결합 단계의 O(n) = O(n log n)
'''

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

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

  return merge(left, right)

def merge(left, right):
  merged = []
  left_index = 0
  right_index = 0

    while left_index < len(left) and right_index < len(right):
        if left[left_index] < right[right_index]:
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1

    while left_index < len(left):
        merged.append(left[left_index])
        left_index += 1

    while right_index < len(right):
        merged.append(right[right_index])
        right_index += 1

    return merged

 

 

O(n^2) 2차 시간

입력 크기(n)가 증가함에 따라 실행 시간이 제곱 배로 증가한다.

# 일반적인 이중 for문
def double_loop(n):
  for i in range(n):
    for j in range(n):
      # do something

 

 

O(2^n) 지수 시간

입력 크기(n)가 증가함에 따라 실행 시간이 두 배씩 증가한다.

ex) 피보나치 수열을 재귀적으로 계산하는 알고리즘 : 각 호출에서 두 개의 새로운 재귀 호출을 생성하므로, 호출 트리는 2^n개의 노드를 가지게 됨. (동적 프로그래밍을 통해 O(n)의 시간 복잡도로 계산 가능)

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

 

 

Big-O 표기법의 수행 시간

 

 

 

코딩 테스트에 시간 복잡도 적용하기

코딩 테스트 문제를 분석 후, 사용할 알고리즘을 적용했을 때 빅오 표기법을 활용하여 제한 시간 내에 결과가 나올 수 있는지 확인할 수 있다. "컴퓨터가 초당 연산할 수 있는 최대 횟수는 1억 번이다."를 전제로 한다.

대략적인 예측을 위한 것일 뿐, 절대적인 것은 아니다.

 

 

 

---

참고

https://wikidocs.net/222560

https://wikidocs.net/206251

https://jettstream.tistory.com/304

https://velog.io/@ka0ka0ka/알고리즘시간-복잡도란

https://velog.io/@wlwl99/시간복잡도-Time-Complexity

https://blog.bitsrc.io/binary-search-in-typescript-e999dd3fca5e

https://swdevnotes.com/swift/2021/fibonacci-sequence-recursion/