시간복잡도와 공간복잡도 · 알고리즘 노트

개념

입력 크기와 연산 횟수

같은 답을 구하는 코드라도 입력이 커지면 실행 시간의 차이가 커집니다. 시간복잡도는 입력 크기에 따라 필요한 연산 수가 어떻게 증가하는지 나타냅니다.

원소가 $N$ 개인 배열을 한 번 확인하면 확인 횟수는 $N$ 번입니다. 모든 두 위치를 각각 확인하면 $N^2$ 번입니다. $N=1\,000$ 일 때 두 횟수는 $1\,000$ 과 $1\,000\,000$ 입니다.

빅오 표기

빅오 표기 $O(f(N))$ 는 입력 크기가 커질 때 연산 수의 증가를 $f(N)$ 에 비례하는 상한으로 나타냅니다. 연산 수가 $3N+5$ 이면 상수 배와 낮은 차수의 항을 생략하여 $O(N)$ 으로 씁니다. $N^2+2N$ 은 $O(N^2)$ 입니다.

최악의 입력을 기준으로 표기하는 경우가 많습니다. 중간에 답을 찾고 종료하는 탐색도 마지막까지 확인해야 하는 경우가 있다면 최악 시간은 $O(N)$ 입니다.

반복문의 복잡도

처리 방식	연산 수	시간복잡도
크기와 무관한 계산 한 번	일정	$O(1)$
길이 N을 한 번 순회	$N$	$O(N)$
길이 N인 반복문을 연속 두 번 수행	$2N$	$O(N)$
각 원소마다 전체 N개 확인	$N^2$	$O(N^2)$
i번째 원소 뒤의 원소만 확인	$N(N-1)/2$	$O(N^2)$
범위를 반복해서 절반으로 축소	약 $\log_2 N$	$O(\log N)$

중첩 반복문은 각 반복 횟수를 함께 확인합니다. 두 포인터처럼 안쪽 반복의 이동 횟수가 전체 실행 동안 $N$ 번으로 제한되면 총 시간은 $O(N)$ 입니다.

입력 크기에 따른 연산 횟수 비교

시간복잡도	사용되는 상황	N = 20일 때 비교할 값
$O(1)$	배열의 한 원소 접근	$1$
$O(\log N)$	이분 탐색	약 $4.3$
$O(N)$	배열 한 번 순회	$20$
$O(N\log N)$	비교 정렬	약 $86$
$O(N^2)$	모든 원소 쌍 확인	$400$
$O(2^N)$	모든 부분집합 나열	$1\,048\,576$
$O(N!)$	모든 순열 나열	약 $2.4\times10^{18}$

표에서 입력 크기가 커질 때 연산 횟수가 얼마나 늘어나는지 비교할 수 있습니다. 실제 실행 시간은 연산 종류, 언어, 실행 환경에 따라서 달라집니다.

입력 제한으로 판단하기

$N=100$ 이면 $N^2=10\,000$ 이지만, $N=100\,000$ 이면 $N^2=10^{10}$ 입니다. 제한에 최대 입력 크기를 대입하여 반복 횟수를 계산한 뒤 시간 제한과 비교합니다. 같은 복잡도라도 문자열 복사나 컨테이너 생성처럼 비용이 큰 작업이 반복되는지도 확인합니다.

공간복잡도

공간복잡도는 입력 크기에 따라 사용하는 메모리가 얼마나 증가하는지 나타냅니다. 길이 $N$ 의 배열은 $O(N)$ , $R\times C$ 배열은 $O(RC)$ 입니다. 재귀 호출은 아직 끝나지 않은 호출의 정보를 저장하므로 최대 깊이가 $D$ 이면 호출 공간은 $O(D)$ 입니다.

추가 공간은 이미 주어진 입력을 저장하는 공간을 제외하고 계산 과정에서 새로 사용하는 공간입니다. 아래 예제는 개수만 누적하므로 추가 공간은 $O(1)$ 입니다.

예제의 연산	시간복잡도	공간복잡도
한 원소씩 세기	$O(N)$	추가 $O(1)$
서로 다른 위치의 쌍 세기	$O(N^2)$	추가 $O(1)$

예제

문제

번호가 $1$ 부터 $N$ 까지인 원소가 있다. 원소의 개수와, 작은 번호를 먼저 적어 두 원소를 고르는 쌍의 개수를 구하여라.

입력

첫째 줄에 양의 정수 $N$ 이 주어진다. $1\le N\le100$ 이다.

출력

첫째 줄에 원소의 개수, 둘째 줄에 쌍의 개수를 출력한다.

3.1 Time & Space Complexity

개념

입력 크기와 연산 횟수

빅오 표기

반복문의 복잡도

입력 크기에 따른 연산 횟수 비교

입력 제한으로 판단하기

공간복잡도

예제

문제

입력

출력

예제 입력

예제 출력

예제 코드