시간 복잡도와 빅오 표기법

시간 복잡도란 어떤 알고리즘을 수행하는데 걸리는 시간을 설명하는 계산 복잡도를 말한다.

• 수행 시간은 컴퓨터 하드웨어, 프로그래밍 언어의 컴파일러에 따라 차이가 있을 수 있기 때문에 오직 명령어의 실행횟수만 고려한다.
• 시간 복잡도를 표기하는 대표적인 방법으로 최고 차항만 나타내는 빅오 표기법이 있다.

빅오 표기법 (Big-O)

$g(n)$을 감싸는 상한선(Upper Bound)인 $c * f(n)$을 빅오(Big-O)라고 한다. 이 때 $N$은 기준점으로 N 이상의 매우 큰 데이터만을 고려한다. 빅오의 자세한 정의는 다음과 같다.

정리하면 입력 크기 $n$과 총 연산횟수가 대응되는 함수 $g(n)$이 있다고 할 때, 이 함수를 포함하는 상한선이 빅오인 것이다. 그렇기 때문에 $g(n)$을 포함하기만 하면 모두 빅오라고 할 수 있다.

빅오 정의에 대한 그래프

빅오 표기법 종류

빅오 표기법 종류

• $O(1)$, 상수 시간: 입력값이 커도 실행시간이 일정하다.
  • ex. 인덱싱
• $O(\log n)$, 로그 시간: 실행 시간이 특정 요인으로 줄어든다. 즉, 입력을 모두 볼 필요가 없다.
  • ex. 이진 탐색, 이진 트리 탐색
• $O(n)$, 선형 시간: 입력값만큼 실행 시간에 영향을 받는다. 즉, 입력을 모두 한 번은 봐야 한다.
  • ex. 정렬되지 않은 배열에서 요소 탐색
• $O(n \log n)$, 선형 로그 시간: 입력값이 커질수록 실행 시간이 로그배만큼 증가한다.
  • ex. 퀵 정렬, 병합 정렬
• $O(n^2)$, 2차 시간: 입력값의 제곱만큼 실행 시간이 걸린다.
  • ex. 버블 정렬, 삽입 정렬

헷갈릴 수 있는 개념: 상한 vs 최악

• 빅오는 최악의 경우를 의미한다 ❌
• 빅오는 상한을 의미한다 ⭕

빅오는 알고리즘의 최악의 경우는 아니라 어떤 함수의 상한선을 의미한다. 예를 들어, 최악의 경우 입력 크기 $n$에 대해 총 연산 횟수가 $5n^2+4$가 나왔다고 하자. 이 연산 횟수를 빅오로 표기했을 때 $O(n^2)$인 것이다. 단순 표기법일 뿐, 알고리즘 최악의 경우와 헷갈리지 말자.

시간 복잡도 계산하는 방법

여러 블로그를 참고해봤을 때, 시간복잡도를 계산하는 가장 좋은 방법은 직접 연산 횟수를 세보는 것이다. 이 때 고려해야할 요소와 연산은 다음과 같다.

• 요소: 반복문, 조건문, 재귀 호출
• 연산: 비교 연산, 대입 연산

반복문과 조건문, 재귀 호출은 연산 횟수에 영향을 끼치며, 이 때 기준으로 삼을 연산을 비교와 대입 연산으로 하면 된다. 다음의 간단한 예시를 보자.

count = 0
for i in range(n):
    for j in range(n):
        count += 1

count는 대입 연산을 하고 있다. 이 때, 대입 연산이 몇 번 이루어질까? 첫 번째 반복문에 의해 $n$번이 이루어진다. 그리고 각 이터레이션에 대해 두 번째 반복문에 의해 또 $n$번이 이루어진다. 그렇기 때문에 위의 예시의 시간 복잡도는 $O(n^2)$으로 계산할 수 있다.

입력 범위로 시간복잡도 예측하기

코딩테스트에서 쓰일 수 있는 팁이다. 알고리즘 문제를 보면 입력의 범위와 시간 제한이 적혀 있다. 보통 연산 횟수 $10^8$인 경우 실행 시간은 약 1초가 인데, 이 사실을 이용하면 알고리즘이 어떤 시간 복잡도를 가져야할지 알 수 있다.

시간 제한이 1초라고 가정할 때, 구현해야할 알고리즘의 시간 복잡도는 다음과 같다.

참고 자료

• 4.1장. 빅오 - 파이썬 알고리즘 인터뷰
• [Algorithm] 알고리즘 시간복잡도에 대하여 - 코딩팩토리
• 알고리즘의 시간 복잡도와 Big-O 쉽게 이해하기 - Chulgil.Lee
• 내 알고리즘의 시간 복잡도를 어떻게 계산할까? - 개발하는 피자 양목장
• Time Complexity: 시간복잡도 구하는 법 + 코딩 팁 - 채니의 블로그