1. 시간 복잡도
1-1. 시간 복잡도란?
1-2. Big-O 표기법
2. 예제
2-1. O(1)
2-2. O(n)
2-3. O(n²)
2-4. O(n³)
2-5. O(nm)
2-6. O(2ⁿ)
2-7. O(logn)
3. 그 외
3-1. 상수항 무시
3-2. 영향력이 낮은 항 무시
3-3. 대략적인 소요시간 추측하기
1. 시간 복잡도
1-1. 시간 복잡도란?
우리가 작성한 코드는 실행시간이 얼마나 걸릴까?
실행해보기 전에 정확한 시간을 추측하는 것은 힘들겠지만
반복문을 몇 번 사용했는지, 입력값은 어떻게 되는지 등을 통해 대략적으로 이 정도 되겠구나.. 를 추측할 수 있다.
즉, 우리는 입력값과 연산 수행 시간의 상관관계를 나타내는 척도를 시간 복잡도라고 한다.
1-2. Big-O 표기법
같은 알고리즘을 가지고 테스트를 하더라도 입력 값이 달라짐에 따라 수행 시간은 매우 짧아질 수도, 매우 길어질 수도 있다.
2 |
1 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
예를 들어 10개의 배열에 위처럼 숫자가 들어가 있다고 치자.
이 숫자를 오름차순으로 정렬하려면 '2'와 '1'만 바꿔주면 된다. 수행 시간이 아주 짧을 것이다.
10 |
9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
하지만 만약 숫자가 처음부터 이렇게 들어가 있었다면...?
분명 수행 시간이 더 오래 걸릴 것이다. 오름차순 정렬하기에는 가장 최악의 상황인 것이다.
시간 복잡도는 보통 이런 최악의 상황일 때 걸리는 시간을 이용해 나타낸다.
그리고 이걸 Big-O 표기법이라고 한다.
그 외 다른 표기법은 여기에서 확인할 수 있다.
하지만 거의 대부분 Big-O 표기법을 이용해 시간 복잡도를 나타낸다.
1-3. 자료의 수에 따른 실행시간 변화
for(int i=0; i<n; i++) {
System.out.println(n);
}위 코드는 n번을 반복하면서 값을 출력하는 예제이다.
즉, 자료의 수는 n개이며 Big-O 표기법에 따라 O(n)이라고 나타낼 수 있다.
자료의 수가 증가함에 따라 소요되는 처리시간 증가율을 그래프로 나타낸 것이다.
빨간색 영역에 가까워질수록 수행 시간이 굉장히 오래 걸리는 알고리즘이라 할 수 있고
초록색에 가까워질수록 수행 시간이 짧은 알고리즘이라 할 수 있다.
각각에 대한 예제는 [목차 2]에서 이어서 알아보자.
2. 예제
2-1. O(1)
if(n%2 == 0) {
System.out.println("짝수");
} else {
System.out.println("홀수");
}위 예제는 입력한 n이 짝수면 한 단계에 걸쳐 수행이 완료되었을 거고
홀수면 두 단계에 걸쳐 수행이 완료되었을 것이다.
하지만 우리는 이걸 O(1), O(2) 이렇게 나누지 않고 전부 O(1)으로 나타낸다.
앞으로 나올 예제들에 비하면 터무니없이 작은 차이이기 때문에 이런 상수들은 전부 O(1)으로 나타내는 것이라 생각하면 된다.
O(1)과 O(2)의 차이에 대한 의견들은 여기에서 확인할 수 있다.
2-2. O(n)
for(int i=0; i<n; i++) {
System.out.println(n);
}반복문을 이용해 n번 반복한다면 이는 Big-O 표기법으로 O(n)이라 나타낼 수 있다.
n의 값에 따라 처리수도 1:1 비례해서 늘어난다.
2-3. O(n²)
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
System.out.println(n * j);
}
}반복문이 두 번 겹쳐져 있는 이중 반복문의 경우는 O(n²)으로 나타낼 수 있다.
아주 쉽죠?
2-4. O(n³)
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
for(int k=0; k<n; k++) {
System.out.println(n * j + k);
}
}
}당연하게도 반복문이 세 번 겹치면 O(n³)이고 이런 식으로 얼마든지 반복문을 겹칠 수 있겠으나
내 경험상 시간 복잡도가 O(n²)만 넘어도 코딩 테스트에선 시간 초과가 뜬다. 약간 마지노선 느낌?
2-5. O(nm)
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
System.out.println(n * m);
}
}얼핏 보면 [목차 2-3]과 같은 이중 포문 같지만 엄연히 다르다.
n번 반복하는 반복문을 두 번 중첩시킨 것이 아니라
n번 반복문과 m번 반복문을 중첩시켰다.
막말로 n이 999999999999999인데 m은 1일 수도 있기 때문에 [목차 2-3]과 달리 O(nm)이라고 나타내 주어야 한다.
2-6. O(2ⁿ)
public static int pibo(int n) {
if (n == 0) return 0;
else if (n == 1) return 1;
return pibo(n - 1) + pibo(n - 2);
}
위 코드는 피보나치수열을 구현한 것이다.
pibo(n)을 호출하면 pibo(n-1)과 pibo(n-2)가 호출된다.
그리고 이 호출 작업은 총 n번 반복되기 때문에 이를 Big-O 표기법으로 나타내면 O(2ⁿ)이 된다.
2-7. O(logn)
public static int binarySeacrh(int[] num, int target, int low, int high) {
int mid = (low + high) / 2;
if(target == num[mid]) return mid;
else if(target < num[mid]) return binarySeacrh(num, target, low, mid-1);
else return binarySeacrh(num, target, mid+1, high);
}위 코드는 이진 탐색 기법을 코드로 구현한 것이다.
탐색을 해나갈수록 탐색해야 할 데이터가 절반으로 뚝뚝 떨어지기 때문에
이를 Big-O 표기법으로 나타내면 O(logn)이 된다.
3. 그 외
3-1. 상수항 무시
if(n%2 == 0) {
System.out.println("짝수");
} else {
System.out.println("홀수");
}
for(int i=0; i<n; i++) {
System.out.println(n);
}위 코드는 [목차 2-1]과 [목차 2-2]의 코드를 합친 것이다.
O(1)과 O(n)이 합쳐져 O(n+1)이라고 표현해야 할 것 같지만 Big-O 표기법에서는 상수항을 무시하는 것이 규칙이다.
즉, O(n)이 된다.
for(int i=0; i<n; i++) {
System.out.println(n);
}
for(int i=0; i<n; i++) {
System.out.println(n);
}마찬가지로 위 코드도 O(n)이 두 번 반복되니 O(2n)이 되어야 할 것 같지만 O(n)이 된다.
3-2. 영향력이 낮은 항 무시
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
System.out.println(n * j);
}
}
for(int i=0; i<n; i++) {
System.out.println(n);
}위 코드는 O(n²)와 O(n)이 합쳐져 O(n²+n)이 될 것 같지만 유감스럽게도 O(n²)이 된다.
n²에 비해서 n은 영향력이 낮으므로 이를 무시하고 표기하는 것이 규칙이다.
앞서 상수항과 영향력이 낮은 항을 무시하는 이유는 Big-O 표기법이 실제 소요시간을 나타내기 위한 방법이 아니라
자료의 수가 증가함에 따라 소요시간이 얼마나 증가하는지를 나타내기 위한 방법이기 때문이다.
3-3. 대략적인 소요시간 추측하기
O( ) <- 이 괄호 안에 들어가는 식을 계산해서 1억당 1초 정도로 생각할 수 있다고 한다.
예를 들어 n이 1억인데 시간 복잡도가 O(n)이면 소요시간이 1초정도 걸린다는 뜻이다.
n이 1억, m이 10, 시간 복잡도가 O(nm)이면 소요시간이 10초가 된다는 것이다.
이렇게 대략적인 소요시간을 코딩하기 전에 추측해봄으로써
주어진 제한 시간 안에 답을 구할 수 있는지 확인할 수 있다.
(하지만 막상 코테를 보면 정신없이 풀기 바빠서 확인할 시간조차 없다는 게 현실... 😭)
💡 느낀 점
- 내가 생각했을 땐 시간 복잡도라는 이름을 바꿔야 한다. 괜히 복잡해 보이고 어려워 보이잖아(?!) 그래서 내가 알고리즘 공부를 소홀히 한 게야.. 암.. 그렇고 말고..
- 회사 면접에서 코딩 테스트 때 작성한 코드의 시간 복잡도는 어느 정도가 될 것 같냐라는 질문을 할 때가 있다고 한다. 그때 오늘 배운 개념으로 자신 있게 대답하고 대략적인 소요시간까지 대답할 수 있다면 좋은 점수를 받을 수 있을 것 같다.
- 소요시간을 단축시킬 수 있는 알고리즘들은 중요한 것임에 틀림없으나 많은 개발자들이 무신경하다고 한다. (나무위키 피셜)
- 워낙 인터넷 속도나 컴퓨터 등이 발전해서 예전에 비해 중요도가 떨어졌겠지만 그래도 개발자라면 관심을 가지고 어떻게 하면 시간을 단축시킬 수 있을까 고민해봐야 한다고 생각한다. 모두가 좋은 인터넷, 컴퓨터 환경을 가지고 있다면 또 모르겠지만 세상에는 그렇지 못한 나라, 사람들도 많으니까..
📘 참고한 자료
- 시간 복잡도 - 나무위키
- Big-O Algorithm Complexity Chart
- 시간복잡도란 무엇일까? - 김초희님 블로그
- 빅오(Big-O 표기법) 완전정복 - 엔지니어 대한민국 (이 분 영상 전부 최고. 구독 좋아요 알림설정까지!!)
댓글