한 줄 정리
- 내 풀이가 1억 번 이하의 연산이 나온다면 시간 초과가 나지 않을 확률이 높다.
- 내 풀이가 5000만 개 이하의 공간을 할당하는 코드라면 메모리 초과가 나지 않을 확률이 높다.
1. 시간 복잡도
•
시간 복잡도란?
◦
시간 복잡도는 프로그램이 입력 크기에 대해 얼마나 빠르게 실행되는지를 나타낸다.
◦
시간 복잡도를 표기할 때는 빅오 표기법(Big-O notation)을 사용하여 표현한다.
(보통, 시간 복잡도라고 하면 빅오 표기법을 의미함)
•
빅오 표기법 (Big-O notation
◦
프로그램 동작 시간에 가장 큰 영향을 주는 값을 중심으로 시간복잡도를 표기함.
◦
프로그램 동작 시간에 대한 대략적인 시간 복잡도를 표기함.
빅오 표기법 작성 예시
문제에서 자주 등장하는 시간 복잡도
•
시간 제한에 따른 연산 횟수
◦
1초 = 1억 번의 연산 이라고 생각하시면 됩니다.
2. 공간 복잡도
•
공간 복잡도란?
◦
공간 복잡도는 프로그램이 얼마나 많은 메모리를 사용하는지를 나타낸다.
◦
공간 복잡도는 문제를 풀 때 크게 신경써야 할 부분은 아님.
◦
공간 복잡도의 표기도 (시간 복잡도와 마찬가지로) 빅오 표기법으로 표현한다.
•
메모리 제한에 따른 허용 공간
◦
int 자료형 기준으로 1MB = 100만 개의 공간 이라고 생각하시면 됩니다.