시간복잡도란 입력 크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간이며, 주요 로직의 반복 횟수를 중점으로 측정된다.
시간이라는 개념은 여러가지 요소에 영향을 받는다. 따라서 시간복잡도를 이야기 할 때는 시간이 아니라 어떠한 알고리즘이 주어진 입력 크기를 기반으로 어떠한 로직이 몇 번 반복되었는가를 중점으로 설명한다.
for (int i = 0; i < 10; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
if (true) {
cout << i << '\n';
}
}
}
}
for (int i = 0; i < n; i++) {
if (true) {
cout << i << '\n';
}
}위의 코드는
위의 수식을 빅오 표기법으로 나타내면
빅오 표기법이란 복잡도에 가장 영향을 많이 끼치는 항의 상수인자를 빼고 나머지 항을 없애서 복잡도를 나타내는 표기법이다.
위의 수식에서 복잡도에 가장 영향을 끼치는 항은
위의 그림에서 확인할 수 있듯
상수시간 시간복잡도는 입력크기와 상관없이 일정한 시간복잡도를 가지는 것을 의미하며,
예를 들어 다음과 같은 부분들이 모두
입력과 출력
cin, cout, scanf, printf
곱하기
a[2] *= 2;
이 외에도 곱하기, 나누기, 나머지연산, 빼기, 간단한 if문, 배열의 인덱스 참조 등은 상수시간 시간복잡도를 가진다.
배열 (array)
- 참조:
$O(1)$ - 탐색:
$O(n)$
배열 (vector)
- 참조:
$O(1)$ - 탐색:
$O(n)$ - 맨 끝, 앞에서 삽입 / 삭제:
$O(1)$ - 중간에 삽입 / 삭제:
$O(n)$
스택 (stack)
- n번째 참조:
$O(n)$ - 가장 앞부분 참조:
$O(1)$ - 탐색:
$O(n)$ - 삽입 / 삭제 (n번째 제외):
$O(1)$
큐 (queue)
- n번째 참조:
$O(n)$ - 가장 앞부분 참조:
$O(1)$ - 탐색:
$O(n)$ - 삽입 / 삭제 (n번째 제외):
$O(1)$
연결 리스트 (doubly linked list)
- 참조:
$O(n)$ - 탐색:
$O(n)$ - 삽입 / 삭제:
$O(1)$
맵 (map)
- 참조:
$O(\log n)$ - 탐색:
$O(\log n)$ - 삽입 / 삭제:
$O(\log n)$
공간복잡도는 입력크기에 대해 어떠한 알고리즘이 실행되는데 필요한 메모리 공간의 양을 가리킨다.
이는 정적변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함하여 어떠한 요소를 담을 공간일 경우 모두 적용된다.
이러한 공간복잡도의 개념은 문제를 해결할 때는 잘 사용되지 않는다.
보통 문제를 해결할 때 배열의 범위 등을 생각하는 2가지 방법을 기반으로 한다.
- 최대 범위
- 메모리 제한
누적합이란 요소들의 누적된 합의 의미로 어떠한 배열을 기반으로 앞에서부터 요소들의 누적된 합을 저장해 새로운 배열을 만들어 이를 활용하는 것을 의미한다.
이는 앞에서부터 더하는 prefix sum과 뒤에서부터 더하는 suffix sum이 존재한다.
예를들어, 1, 2, 3, 4 라는 배열의 누적합은 1, 3, 6, 10 이라는 배열이 된다.
이와 같이 누적합 배열을 만들어놓으면 구간 쿼리에 대응하기 쉬워진다.
문제를 풀 때, 구간에 대한 많은 쿼리가 나올 때 생각해야 되는 것은 트리와 누적합이다. 구간 내의 요소들의 변하지 않는 정적 요소일 경우 누적합을 사용할 수 있다.
for (int i = 1; i <= n; i++) {
cin >> a[i];
psum[i] = psum[i - 1] + a[i];
}위의 코드에서는 a[i] 를 입력받고, 해당 값을 누적합 배열에 쌓아간다.
이를 구간에 대해 사용할 때는 다음과 같이 사용할 수 있다.
cout << psum[c] - psum[b - 1] << '\n';다음과 같이 사용하는 경우 b에서 c까지 합을 구하라는 문제에 대하여