[Algorithm] 시간복잡도
시간 복잡도 Time Complexity
- 입력 값과 연산 수행 시간의 상관관계를 나타내는 척도
알고리즘을 풀 때, 다음과 같이 시간 초과가 나는 경우가 본 적이 있을 것이다.
- 이와 같이, 알고리즘은 효율성도 중요한 척도이기 때문에, 계산하는 방법을 알아야한다!
시간 복잡도 표기법, 빅오 표기법(Big-O)
시간 복잡도를 나타내기 위한 기법으로 3가지가 존재한다.
⇒ 따라서, 우리는 항상 빅오 표기법을 활용한 시간 복잡도 계산을 알아야한다!
빅오 표기법의 시간 복잡도 단계
- 빅오 표기는 입력된 N의 크기에 따라 실행되는 연산 횟수로 시간 복잡도를 표현한다.
시간복잡도의 단계는 아래와 같이 크게 나눠볼 수 있다.
⇒ 여기서, 우리는 2차 시간을 더 빠른 시간으로 줄일 수 없는가를 생각해봐야한다!
시간복잡도 단계
- 앞서 봤던, 시간 복잡도 단계별로 예제를 제시해보겠다.
입력은 항상 N(또는 M)으로 주어진다고 생각하겠다.
💡 단계를 평가하는 기준은 항상 N이 1부터 늘어나는 반복 횟수임을 알아야 한다!
1️⃣ O(1) 상수 시간
1
int sum = (N + 1) * N / 2;
- 위와 같은 예시는 흔히, 2차 시간이라 오해할 수 있다!
실제 연산 횟수를 확인해보면, 다음과 같이 4번이다.
⇒ 따라서 총 연산 횟수 4 = O(1)에 가까우므로 상수시간이 된다.
왜 상수 시간이냐고 하면은 N과 관계 없는 연산이기 때문이다.
결론으로! N의 영향을 받지 않는 사칙 연산을 제외한 대입 연산이 1회 일어나므로,
위와 같은 예제는 상수 시간으로 평가하면 된다.
2️⃣ O(log n) 로그 시간
1
2
3
4
5
int i = 1;
while (i < N) {
System.out.println(i);
i = i * 2;
}
앞서 상수 시간에서, 사칙 연산은 N과 관계 없는 연산임을 알았다면 다음과 같이 평가할 수 있다.
근데 N과 관계 된 i가 거듭제곱으로 커지고 있으므로, 다음과 같은 평가 가능하다.
결론으로! N이 1부터 하나씩 차례로 반복하는 것이 아닌,
거듭제곱으로 건너 뛰면서 반복하므로, 로그 시간으로 평가할 수 있다!
💡 대표 예시: 이진 탐색 알고리즘
3️⃣ O(n) 선형 시간
1
2
3
4
5
int sum = 0;
for (let i = 0; i <= N; i++) {
System.out.println(i);
sum += i;
}
이 예제처럼, i가 0부터 하나씩 커지면서 N까지 반복하면 선형 시간으로 평가할 수 있다.
결론으로, 2N, 3N, 4N, … 씩 나와도 N 앞의 상수 배는 빅오의 영향을 받지 않는다.
따라서, 2N, 3N, 4N, … 모두 선형 시간으로 평가 가능하다.
💡 대표 예시: DFS 알고리즘, DP(Dynamic Programming) 알고리즘
4️⃣ O(n log n) 선형 로그 시간
1
2
int[] intArr = new int[] {1,3,2,5,4};
Arrays.sort(in tArr);
- 선형 로그 시간은 정렬이 보통이 이에 해당한다.
정렬은 병합 정렬, 퀵 정렬, 힙 정렬 등.. 다양한 방법이 존재하지만,
정렬에서 가장 빠른 시간 복잡도는 NlogN으로 평가한다.
결론으로, 길이가 N인 배열을 정렬할 때의 가장 빠른 횟수는 NlogN이므로
해당 연산 횟수를 선형 로그 시간으로 평가하도록 한다.
💡 대표 예시: 정렬 알고리즘
5️⃣ O(n^2) 2차 시간
1
2
3
4
5
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.println(i + ", " + j);
}
}
- 결국, 가장 많이 나오는 케이스가 위와 같은 경우이다.
- 위와 같이 N이 주어졌을 때, 각 원소를 다른 모든 원소랑 비교하는 경우가 2차 시간에 해당한다.
결국 코딩테스트의 시간 복잡도를 줄이는 방법은
위와 같은 예제를 다른 알고리즘이나 방법으로 줄여나가는 과정이다!
💡 대표 예시: 완전 탐색
시간복잡도 계산
백준 문제 시간 제한
백준 문제는 다음과 같이 시간 제한이 존재한다.
- 여기서 말하는 1초는 10,000,000번(1억번)의 연산 횟수를 의미한다!
- 따라서 테스트에 통과하려면, 앞서 배운 방법을 토대로 연산 횟수를 계산하여
초과하지 않는지를 계산하면 된다.
연산 횟수 계산
- 자 그렇다면, 문제별 연산횟수를 어떻게 계산하는지를 단계별로 알아보자.
1. 시간 제한과 입력 크기(예: N) 제한 확인!
2. 내가 짠 코드의 시간 복잡도 계산
3. 내가 짠 코드의 **효율성** 판단
4. 제출 확인
총정리
- 시간 복잡도의 핵심은 시간 제한이 얼마인지와 입력 크기가 어느 정도로 큰지를 확인하는 것이다.
입력 크기는 다음과 같이 ~로 주어진다에 문구에 유의하며 확인해보록 하자!
✨ 출처
Blog, [algorithm] 시간복잡도란? 시간복잡도 계산하는법 ( O(1), O(n), O(log n))