시간 복잡도와 공간 복잡도

한 줄 정리 - 내 풀이가 1억 번 이하의 연산이 나온다면 시간 초과가 나지 않을 확률이 높다. - 내 풀이가 5000만 개 이하의 공간을 할당하는 코드라면 메모리 초과가 나지 않을 확률이 높다.

1. 시간 복잡도

• 시간 복잡도란?
• 시간 복잡도는 프로그램이 입력 크기에 대해 얼마나 빠르게 실행되는지를 나타낸다.
• 시간 복잡도를 표기할 때는 빅오 표기법(Big-O notation)을 사용하여 표현한다. (보통, 시간 복잡도라고 하면 빅오 표기법을 의미함)

• 빅오 표기법 (Big-O notation
• 프로그램 동작 시간에 가장 큰 영향을 주는 값을 중심으로 시간복잡도를 표기함.
• 프로그램 동작 시간에 대한 대략적인 시간 복잡도를 표기함.
빅오 표기법 작성 예시

빅오 표기법은 표기할 때만 사용하고, 문제를 풀 때는 실제 연산 횟수를 계산하는 것이 좋음.
 
문제에서 자주 등장하는 시간 복잡도

 

• 시간 제한에 따른 연산 횟수
• 1초 = 1억 번의 연산 이라고 생각하시면 됩니다.

2. 공간 복잡도

• 공간 복잡도란?
• 공간 복잡도는 프로그램이 얼마나 많은 메모리를 사용하는지를 나타낸다.
• 공간 복잡도는 문제를 풀 때 크게 신경써야 할 부분은 아님.
• 공간 복잡도의 표기도 (시간 복잡도와 마찬가지로) 빅오 표기법으로 표현한다.

• 메모리 제한에 따른 허용 공간
• int 자료형 기준으로 1MB = 100만 개의 공간 이라고 생각하시면 됩니다.