소개
지하철을 탈 때, 4~5 정거장을 가야할 때, 급행과 일반이 있다면 어느것을 타도 상관이 없다.
하지만 20~30 정거장을 가야할 때는 무조건 급행을 탈것이다. 시간이 차이가 많이 날테니까,
실제로 대부분의 사람들은 어디서 환승을 하고 어디로 가야 가장 빠른 시간에 도착지에 도착할 수 있는지 심지어 어느 칸에 타야 더 빠른 환승이나 출구로 갈 수 있는지를
지하철 앱을 통해서 미리 검색을 하고 지하철을 탈 것이다.
알고리즘
여기서 지하철을 타고 목적지에 도착하는 과정을 알고리즘이라 한다.
시간 복잡도
시간 복잡도(Time Complexity)는 알고리즘을 수행하는 데 연산들이 몇 번 이루어지는 지를 숫자로 표기한다.
지나온, 지나갈 정거장의 수를 시간복잡도로 나타낼 수 있는데,
최소 정거장으로 도착지까지 가는가? = 얼마나 연산을 적게 했는가? 는 같은 의미이다.
따라서 지하철앱에서 가장 빠른 노선을 선택하는 것은 프로그램 세계 에서 시간 복잡도가 낮은 알고리즘을 채택한다고 볼 수 있다.
여기서 연산의 종류는 산술, 대입, 비교, 이동을 말한다.
빅오 표기법 (Big -O)
시간복잡도를 구하기 위해 연산의 실행횟수를 구하는 과정에서 발생하는 연산들은 보편적으로 그 값이 변하지 않는 상수(Constant)가 아니라 입력한 데이터의 개수를 나타내는 n에 따라 변하게 된다.
따라서, 이런 상수와 같은 연관 없는 연산들만 뽑아내고 입력한 데이터의 개수에 따라 분석도를 표기하는 것을 빅오 표기법이다.
- 빅오 표기법의 시간복잡도는 입력된 N의 크기에 따라 실행되는 조작의 수를 나타낸다.
여기서 가장 중요한 것은 N 인데, N 은 입력한 데이터의 개수를 뜻 한다.
| 복잡도 | 1개 입력 | 10개 입력 | 100개 입력 |
| O(1) | 1 | 1 | 1 |
| O(log N) | 0 | 2 | 5 |
| O(N) | 1 | 10 | 100 |
| O(N log N) | 0 | 20 | 461 |
| O(N^2) | 1 | 100 | 10000 |
| O(2^N) | 1 | 1024 | 1267650600228229401496703205376 |
| O(N!) | 1 | 3628800 | 화면에 표현할 수 없음! |
각 문제의 시간복잡도 유형을 빨리 파악할 수 있도록 아래 예를 통해 빠르게 알아 볼수 있다.
- 하나의 루프를 사용하여 단일 요소 집합을 반복 하는 경우 : O (n)
- 컬렉션의 절반 이상 을 반복 하는 경우 : O (n / 2) -> O (n)
- 두 개의 다른 루프를 사용하여 두 개의 개별 콜렉션을 반복 할 경우 : O (n + m) -> O (n)
- 두 개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우 : O (n²)
- 두 개의 중첩 루프를 사용하여 두 개의 다른 콜렉션을 반복 할 경우 : O (n * m) -> O (n²)
- 컬렉션 정렬을 사용하는 경우 : O(n*log(n))
반복문이 두개가 있는것은 n이지만 반복문이 중첩되는 순간 n² 가 된다.
더하기 시간분석도 구하기
// n 번 까지의 자연수의 합을 구하는 기능
public static int count1(int n) {
int sum = 0;
for (int i = 1; i <= n; i++) {
sum += i;
}
return sum;
}
// n 번 까지의 자연수의 합을 구하는 기능
public static int count2(int n) {
return (n + 1) * n / 2;
}
count1 은 1부터 N까지 반복문을 돌면서 합을 직접 계산하고, count2는 등차수열의 합 공식을 통해 합을 계산한다.
count1의 연산
int sum = 0; -> 1, 처음에 한번
int i = 1; -> 1, 처음에 한번
i++ -> N, 반복(N) 만큼 연산
sum += i -> N, 반복(N) 만큼 연산
총 합하면 1 + 1 + N + N = 2N + 2
count2의 연산
N + 1 -> 1번
* N -> 1번
/ 2 -> 1번
= -> 1번, 대입 연산
총 4번
count1 은 입력값의 따라서 2N + 2 이고, count2 는 입력값 과 무관하게 무조건 4번이다.
Big-O 표기법으로 표현하면 4 = O(1) 이므로, 두번째 코드의 시간 복잡도는 O(1) 이다.
java Collection 시간 복잡도/특징 정리 한 좋은 사이트를 발견했다.
출처
madplay.github.io/post/time-complexity-space-complexity
stalk-calvin.github.io/blog/2016/12/10/big-o.html
댓글