시간 복잡도와 빅오 표기법

 

*파이썬 초정독 스터디 - 코딩테스트 합격자되기 파이썬 편 도서를 참고하여 작성된 글입니다.

시간 복잡도란?

• 알고리즘의 성능을 나타내는 지표
• 입력크기 에 대한 연산 횟수의 상한을 의미
• 낮을수록 좋으며, 빠른 속도로 연산할 수 있음

수행 시간을 측정하는 방법

절대 시간 측정

• 말 그대로 실제 수행한 시간을 측정함
• 이 방법은 실행 환경에 따른 영향을 받게 됨시간 복잡도 측정
• 시간복잡도는 알고리즘이 시작한 순간부터 결괏값이 나올 때 까지의 연산횟수를 나타냄
• 배열을 앞에서부터 하나씩 검사하면 최선의 연산 횟수는 1번, 최악은 배열의 요소 n회만큼임.
  • 그러나 이와 같이 특정한 입력 크기에 따른 횟수로 시간 복잡도를 논하는 것은 특정 상황에 대한 것이므로 무의미함
  • 배열의 크기가 1이면 best case와 worst case가 같아지는 상황도 있을 수 있음
  • 따라서 크기를 N으로 일반화하고 연산 횟수의 추이를 나타내야 하며, 입력 크기에 따른 연산 횟수의 추이를 활용하여 시간 복잡도를 표현하는 방법을 점근적 표기법이라 함.
  • 테스트 상황에서는 모든 경우의 수에서 알고리즘이 문제를 처리하는 것을 고려해야 하므로, 시간 복잡도는 최악의 경우를 가정함

빅오 표기법

• 이 때 최악의 경우에 대하여 시간 복잡도를 점근적 상한선을 활용하여 표현하는 방법이 빅오 표기법
• 어떤 프로그램의 연산횟수가 f(x)일 때, 함수의 최고차항을 남기고 차수와 계수를 지워 O(...)로 표기함

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

    for k in range(n):
        count +=1

    for m in range(2*n):
        count +=1
loop(6)

• 이 경우 2중 for문에서 n^2회의 연산이 이루어지고, 두번째 반복문에서 n회의 연산이, 세 번째 반복문에서 2n회의 연산이 이루어짐.
• f(x) = x^2 + 3x로 표현할 수 있음
• 빅오 표기법으로 표기하면 최고차항인 x^2만 남기고, 계수는 1이므로 O(n^2)으로 표기할 수 있음

이 때 의문이 들 수 있는 부분은, 3x가 x^2보다 큰 x의 범위가 분명 존재한다는 점인데, 2차함수 그래프는 반드시 어느 시점부터 1차함수를 역전하기 시작하며, 빅오 표기법은 최악의 경우를 가정하므로 일부 구간에 해당하는 범위를 두고 O(x)로 표기하는 것이 아닌 최악의 경우를 크기 N으로 일반화 하여 표기하는 것이므로 O(n^2)이 적절함.

이와 같은 이유로 빅오 표기법은 정확한 시간을 측정하고자 하는 것이 아닌, 추세 파악에 그 목적이 있으므로 최고
차항만 남기고 이하 차수를 고려하지 않음.

시간복잡도 계산 예제

ex 1

숫자 N을 입력받으면 1부터 N번째 줄 까지 각 줄에 1부터 N개의 별을 출력하는 경우를 살펴보면

def star(N):
    for i in range(N):
        for j in range(i):
            print("*")
start(10)

두번째 반복문에 의해 N번째 줄에는 N번의 연산이 발생함.
따라서 모든 줄의 연산횟수 합은 1+2+..+(N-1)+N = N(N+1)/2 이므로
빅오표기법은 O(n^2).

ex 2

초기 박테리아 세포 갯수가 N이고, 해마다 이전 갯수의 반으로 줄어든다면, 언제 모든 박테리아가 죽는지 계산

초기에 N마리
1년 후 1/2*N
2년 후 1/4*N
...
x년 후 1/2^x*N

f(x) = N(1/2)^x 인데, f(x) < 1 이라는 수식은
N(log2x) >= 1로 변환할 수 있으며

이를 만족하기 위한 x를 찾는 알고리즘의 시간복잡도를 빅오표기법으로 O(logx)로 표기할 수 있음.