[자료구조] 시간복잡도(Time Complexity)

시간 복잡도(Time Complexity)

컴퓨터는 1초에 연산을 몇 번 할 수 있을까?

문제를 풀 때는 대략 1초에서 1억번 정도로 잡는다.

이렇듯 알고리즘 문제를 해결할 때, 코드의 실행 시간과 메모리 사용량은 중요한 요소이다. 효율적인 알고리즘을 작성하려면 어떻게 코드를 구성해야 할지 고민해야 한다. 이 때 중요한 개념 중 하나가 시간 복잡도와 공간 복잡도, Big-O 표기법이다.

 

시간 복잡도란 무엇인가?

알고리즘의 시간 복잡도는 입력값의 크기에 따라 알고리즘이 얼마나 많은 연산을 수행하는지를 나타내는 지표이다. 즉, 내 코드의 실행 시간이 얼마 걸리는지 알 수 있다. 시간 복잡도를 분석하여 입력값이 커질 때 알고리즘의 실행 시간이 어떻게 증가하는지 예측할 수 있다.

메모리는 시간이 흐를수록 효율적으로 발전해서, 중요도가 하락하였다.

그러나 시간복잡도는 여전히 프로그램의 성능을 나타낼 수 있다.

알고리즘에서 더 빠른 코드 == 더 좋은 코드

 

Big-O 표기법이란?

하지만 연산량을 실제로 하나하나 계산하는건 무리가 있다.

Big-O 표기법은 알고리즘의 시간 복잡도를 대략적으로 표현하는 방법 중 하나이다. 이는 알고리즘의 실행 시간이 입력값의 크기에 어떻게 비례하는지를 나타낸다. Big-O 표기법은 다양한 형태로 표현되며, 주로 다음과 같이 나타낸다.

• O(1): 상수 시간. 입력값과 관계없이 고정된 시간이 소요됨.
• O(log N): 로그 시간. 입력값이 증가할수록 연산 횟수가 로그에 비례하여 증가.
• O(N): 선형 시간. 입력값의 크기에 비례하여 연산 횟수가 증가.
• O(N log N): 선형-로그 시간. 선형 시간과 로그 시간의 조합.
• O(N^2): 2차 시간. 입력값의 제곱에 비례하여 연산 횟수가 증가.
• O(2^N): 지수 시간. 2의 입력값 제곱에 비례하여 연산 횟수가 증가.

Big-O	명칭	n = 100	특징
O(1)	상수 시간	1	n값에 상관없이 고정된 시간
O(log N)	로그 시간	약 7	엄청나게 큰 수도 커버 가능
O(N)	선형 시간	100
O(N log N)	선형-로그 시간	700	좋은 알고리즘의 마지노선
O(N^2)	2차 시간	10,000	어려운 문제일수록 제한
O(2^N)	지수 시간	10^30	거의 불가능

일반적으로 최고 차항만 계수를 땐 후 표기 한다.

• 최고 차항만 표기하니까 부정확하다.
• O(100N)과 O(2N)의 시간 복잡도가 똑같다 !!!

시간제한이 1초면 O(N) 기준 N <= 1 ~ 10억 까지는 커버가 가능하다.

 

Space Complexity(공간복잡도)

공간 복잡도는 알고리즘이 얼마나 많은 메모리를 사용하는지를 나타내는 척도이다.

공간 복잡도를 표기할 때도 빅오 표기법을 사용한다.

앞서 시간 복잡도처럼 메모리 사용량에도 절대적인 제한이 있다.

일반적으로 메모리 사용량 기준은 MB 단위로 제시된다.

• 보통 코딩테스트에서 128~512MB로 제한이 있다.
• int의 경우 약 리스트 길이가 100만일 때, 4MB이다.
• 즉, 128MB일 때 3200만개, 256MB일 때 6400만개, 512MB일 때 1억 2800만개 사용 가능하다.

 

효율적인 알고리즘 선택의 중요성

알고리즘 문제를 풀 때는 효율적인 알고리즘을 선택하는 것이 중요하다. 만약 시간 복잡도를 고려하지 않고 작성한 알고리즘이 입력값이 커짐에 따라 급격하게 느려진다면, 시간 제한을 초과하여 정확한 결과를 얻지 못한다. 따라서 Big-O 표기법과 시간 복잡도, 공간 복잡도 개념을 이해하고 이를 활용하여 효율적인 알고리즘을 설계하는 것이 필요하다.