[Algorithm] 시간 복잡도와 빅오(Big-O) 표기법

백준에서 알고리즘 문제를 풀 때, 시간 초과로 인해 문제를 통과하지 못하는 경우가 있다. 이는 작성한 코드의 실행시간이 너무 길게 나와 통과하지 못하는 경우로 알고리즘의 수행 시간을 평가하는 시간 복잡도와 관련이 있다.

 

빅오(Big-O) 표기법

 

시간 복잡도는 알고리즘의 수행 시간을 평가하는 것으로 빅오(Big-O) 표기법을 이용하여 알고리즘의 성능을 나타낸다. 우리는 문제에 맞게 최대한 시간 복잡도를 고려하여 가장 효율적인 알고리즘을 선택하여 사용해야 한다.

 

빅오 표기법의 경은 불필요한 연산을 제거하여 알고리즘 분석을 쉽게 할 목적으로 사용이 된다. 여기서 가장 중요한 것은 중요하지 않은 시간 복잡도를 계산할 때, 중요하지 않은 상수와 계수들을 제거하면 알고리즘 실행시간에서 중요한 성장률에 집중할 수 있는데, 이를 점근적 표기법(Asymptotic notation)이라고 부른다. 즉, 가장 큰 영향을 주는 항만 계산한다는 것이다.

 

예를 들어 아래와 같은 함수 코드가 있다고 생각해보자. (우선 시간 복잡도의 개념을 이해하지 못하더라도 점근적 표기법이라는 개념에 대해 이해해보자.)

def F(n):
	for i in range(n):
    		print(i)
    	for i in range(n):
    		print(i)

 

여기서 위 함수의 시간 복잡도는 O(2n)이라고 표기할 수 있다. 그러나, 빅오 표기법에서는 O(2n)이라고 표기하지 않고 O(n)이라고 표기한다. 왜냐하면, 빅오 표기법은 실제 알고리즘의 러닝 타임을 정확히 재기 위한 개념이 아니고 장기적으로 데이터가 증가함에 따른 처리시간을 표기하는 목적으로 사용이 되기 때문이다. 상수는 고정된 숫자이기에 증가율에 영향을 미칠 때 언제나 고정된 상수만큼만 영향을 미치기 때문에 장기적으로 증가하지 않는 숫자는 빅오 표기법에 제거하겠다는 의미로 생각하면 된다.

 

빅오 표기법은 시간 복잡도 외에도 공간 복잡도를 분석하기 위해서도 사용이 된다. 시간 복잡도가 입력된 N의 크기에 따라 실행되는 조작의 수를 의미한다면 공간복잡도는 알고리즘이 실행될 때 사용되는 메모리의 양을 나타낸다. 공간 복잡도의 경우 요즘에는 데이터를 저장할 수 있는 메모리의 발전으로 중요도가 낮아져 구체적인 설명은 생략한다.

 

아래는 복잡도에 따른 빅오 표기법의 그래프이다.

 

시간 복잡도

 

앞서 언급했던 시간 복잡도의 정의는 알고리즘의 성능, 즉 속도를 평가하는 것이라고 했다. 이는 알고리즘을 수행하기 위해 프로세스가 수행해야하는 연산을 수치화 한것이라고 생각하면 된다.

 

시간복잡도에서 중요하게 보는 것은 가장 큰 영향을 미치는 N의 단위이다.

1			O(1)		-> 상수
2n + 20			O(n)		-> n이 가장 큰 영향을 미침.
3n^2			O(n^2)		-> n^2이 가장 큰 영향을 미침.

 

시간 복잡도의 문제 해결 단계는 아래와 같다.

O(1) – 상수 시간 : 문제를 해결하는데 오직 한 단계만 처리함.
O(log n) – 로그 시간 : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬.
O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐.
O(n log n) : 문제를 해결하기 위한 단계의 수가 N*(log2N) 번만큼의 수행시간을 가진다. (선형로그형)
O(n^2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱.
O(C^n) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱.

 

아래표는 실행시간이 빠른 순으로 정리한 입력 N값에 따른 서로 다른 알고리즘의 시간 복잡도이다.

시간 복잡도	1	10	100
O(1)	1	1	1
O(logn)	0	2	5
O(n)	1	10	100
O(nlogn)	0	20	461
O(n^2)	1	100	10000
O(2^n)	1	1024	126765...
O(N!)	1	3628800	표현 불가

이제 해당 시간 복잡도들에 대해 예시와 함께 자세히 짚어보자.

 

O(1) - Constant

 

O(1) 알고리즘의 경우, 입력 데이터에 상관없이 언제나 일정한 시간이 걸리는 함수를 의미한다.

def hello():
	print("hello_world!")

 

Data에 따른 시간 그래프는 아래와 같이 나타낼 수 있다.

 

O(n) - Linear

 

O(n) 알고리즘의 경우 입력 데이터의 크기에 비례해서 처리 시간이 걸리는 함수이다.

def linear(n):
	for i in range(n):
    		print(i)

Data에 따른 시간 그래프는 아래와 같이 나타낼 수 있다.

 

O(n^2) - Square

 

O(n^2)은 반복문이 2번 있는 케이스를 의미한다. 데이터를 받으면 첫번째 loop를 n번 돌고 각각의 loop에서 또 n번 돌게 되기 때문에 n^2 시간 복잡도가 산출된다.

def square(n):
	for n in range(n):
    		for m in range(n):
        		print(n, m)

Data에 따른 시간 그래프는 아래와 같이 나타낼 수 있다.

 

O(logn), O(nlogn)

 

O(logn)의 대표적인 알고리즘은 바로 이진 검색이다. 아래 같이 오름차순 정렬이 된 Array에서 Key가 6인 값을 찾는다고 가정해보자.

정렬이 되어 있으니 이진 검색을 하려면 우선 가운데 값을 찾아서 Key값(6)과 비교한다. 

Key값이 더 크니까 오른쪽에 있다는 사실을 알 수 있다. 때문에 왼쪽 데이터는 무시한다.

그리고 이전과 같이 다시 남은 데이터를 가지고 다시 Key값과 비교한다. 

Key값이 더 작으니까 앞쪽 데이터를 무시하여 최종적으로 Key값을 찾을 수 있게 된다.

 

이렇게 한번 처리가 진행이 될 때마다 검색해야하는 데이터가 절반씩 줄어드는 알고리즘을 O(logn) 알고리즘이라고 한다.

코드 예제는 아래와 같다.

def binary_search(li, item, first=0, last=None):
	if not last:
		last = len(li)

	midpoint = (last - first) / 2 + first

	if li[midpoint] == item:
		return midpoint

	elif li[midpoint] > item:
		return binary_search(li, item, first, midpoint)

	else:
		return binary_search(li, item, midpoint, last)

Data에 따른 시간 그래프는 아래와 같이 나타낼 수 있다.

 

O(2^n) - Exponential

 

O(2^n)은 빅오 표기법 중 가장 느린 시간 복잡도를 가진다. 이는 재귀로 구현하는 피보나치 수열이 O(2^n)의 시간 복잡도를 가진 대표적인 알고리즘으로 N이 100 이상이면 평생 결과를 반환받지 못할 수 있다...

아래는 O(2^n) 코드 예제이다.

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

Data에 따른 시간 그래프는 아래와 같이 나타낼 수 있다.

 

 

그러나 문제를 보고 각 문제의 시간 복잡도 유형을 빨리 파악하기는 쉽지 않다. 때문에 시간 복잡도 유형을 빨리 파악할 수 있도록 아래 예를 통해 빠르게 알아볼 수 있다.

하나의 루프를 사용하여 단일 요소 집합을 반복하는 경우: O(n)
컬렉션의 절반 이상을 반복하는 경우: O(n/2) = O(n)
두 개의 다른 루프를 사용하여 두 개의 개별 콜렉션을 반복하는 경우: O(n+m) = O(n)
두 개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우: O(n^2)
두 개의 중첩 루프를 사용하여 두 개의 다른 콜렉션을 반복하는 경우: O(n*m) = O(n^2)
컬렉션 정렬을 사용하는 경우: O(n*logn))

---

Reference

 

https://blog.chulgil.me/algorithm/

알고리즘의 시간 복잡도와 Big-O 쉽게 이해하기

https://joyhong-91.tistory.com/12#google_vignette

[algorithm] 시간복잡도란? 시간복잡도 계산하는법 ( O(1), O(n), O(log n))

https://yoongrammer.tistory.com/79

시간 복잡도(Time Complexity) 및 공간 복잡도(Space Complexity)

https://www.youtube.com/watch?v=6Iq5iMCVsXA