[백엔드 기술면접] 시간복잡도(time complexity)
시간복잡도(time complexity)
이번 공부 내용은 유튜브 보고 시간복잡도를 정리했습니다. 참고용으로만 봐주세요~!!
서론
어떤 함수를 실행했을 때 실행시간이 어느 정도 일지 표현하고 싶다.
그런데 이때 실행시간이 컴퓨터 성능마다 다를 수 있다.
이것을 좀 더 간단하게 표현하기 위해서 어떻게 해야할까?
본론
실행시간(running time)이란?
실행시간(running time)은 함수/알고리즘 수행에 필요한 스텝(step) 수라고 할 수 있다.
먼저 코드에 각 라인을 수행하기 위해 필요한 스텝 수는 상수(constant)라고 가정해보자.
아래 코드에서 c1,c2,c3,c4는 각 코드에 라인이라고 가정한다.
int[] multiply(int[]inputs, int multiplier){ // cost times
int[] nums = new int[inputs.length]; // c1 * 1 +
for (int i =0; i<inputs.length; i++) { // c2 * N+1 +
nums[i] = inputs[i] * multiplier; // c3 * N +
}
return nums; // c4 * 1 +
}
각 코스트들을 더하여서 정리를 다시 하면
T(N) = c1 + c2*(N+1) + c3*N + 1 = (c2+c3)*N+ c1+c2+1 = a*N+b
이 때 N이라는 것은 input size의 크기입니다. 즉 input에 들어가는 배열의 크기에 따라서
실행시간이 달라지는 것을 의미합니다.
- 여기서 더 정확한 계산은 어렵다
- N이 작을 땐 실행시간이 의미가 없다.
- N → ∞ 일 때 실행시간이 궁금하다
여기서 맨 마지막 색칠한 부분이 우리가 궁금한 부분이다.
N → ∞ 일 때
- N이 커질수록 덜 중요한 것은 제거
- 최고차항만 의미있다
- 최고차항의 계수는 의미없다
즉 a*N+b에서 a와b는 의미가 없다.
최종적으로 θ(N) 이라고 표현 할 수 있다.
이렇게 N이 커질수록(무한대로 갈수록) 분석하는 방식을, 즉 어떤 함수 형태로 근접해지는지
분석하는 방법을 점근적 분석(Asymptotic analysis) 이라고 한다.
그리고 θ(N) 이것은 점근적 표기법이라고 말한다.
결론
시간복잡도란? 함수의 실행시간을 표현하는 것이고 주로 점근적 분석을 통해 실행시간을
단순하게 표현하며 이 때 점근적 표기법으로 표현을 합니다.
점근적 표기법을 case별 예제를 통해서 분석
boolean exists(int[]inputs, int target){
for(int i = 0; i < inputs.length; i++){
if(inputs[i]==target){
return true;
}
}
return false;
}
이 함수의 시간복잡도를 구해보자!
그런데 여기서 고려해야할 것은 함수의 파라미터 데이터에 따라 실행시간이 조금씩 다를 것 같다.
// 52 | 7 | 34 | ... | ... | 86 |
// 0 1 2 N-1
target이 왼쪽 부분일지(52,7,34), 오른쪽 부분(86)에 속할지 모른다.
case로 분류했을 때 아래와 같이 나타낼 수 있다.
| case | when | times |
|---|---|---|
| best | 0번째에 존재 | 1 |
| worst | 마지막에 존재 or 존재하지 않음 | N |
lower bound(하한선)
함수 실행 시간은 아무리 빨라도 상수시간 이상입니다.
upper bound(상한선)
함수 실행 시간은 아무리 오래걸려도 N에 비례하는 정도 이하입니다.
즉 함수의 실행시간은 하한선을 기준으로 설명할 수 있고, 상한선을 기준으로 설명 할 수 있다.
이것을 점근적으로 표현하게 되면 lower bound = Ω(1), upper bound = O(N)으로 표현 할 수 있다.
여기서 1은 inputsize와 상관없이 상수시간이 걸린다는 의미이고, N은 input size가 N에 비례한다.
| – | best | worst | Avg |
|---|---|---|---|
| Ω | Ω(1) | Ω(N) | |
| O | O(1) | O(N) | O(N) |
| θ | θ(1) | θ(N) |
θ은 이렇게 상한선과 하한선이 아주 타이트하다 해서 tight bound라고 한다.
점근적 표기법 case를 정리하면
| 점근적 표기법 | |
|---|---|
| Ω | lower bound |
| O | upper bound |
| θ | tight bound |
| case 분류 | |
|---|---|
| best | 최단시간 실행 |
| worst | 최장시간 실행 |
| average | 일반적인 실행 |
최종적으로 위 예제코드는 θ(N)으로 표현할 수 있다.
Binary search 시간복잡도 구하기
int findPosition(int[] sortedinputs, int target){
...
}
Binary search는 이미 정렬이된 배열을 input으로 받고 그 배열에서 내가 관심있는
target을 찾거나 위치를 반환을 하는 것이다.
worst case: 찾는게 없을 때
// target = 105
// 0 | 10 | 20 | 30 | 40 | 50 | 60 | 70 | 80 | 90 | 100 | 110 | 120 | 130 | 140 |
// 가운데서 시작을 함 => 70 밑으로는 필요가 없다
// | 80 | 90 | 100 | 110 | 120 | 130 | 140 |
// 110 > 105
// | 80 | 90 | 100 |
// 90 < 105 즉 찾는게 없다.
여기서 매번 실행 할 때마다 1/2씩 사이즈가 줄어든다. 몇 번만에 사이즈는 1이 되는가?
input size를 N이라고 했을 때, N*(1/2)^k = 1 k를 구하는게 핵심이다.
N/2^k = 1 로 다시 정리할 수 있고 최종적으로 k=log2N 이 된다.
이것을 점근적 표기법으로 표현하면 θ(logN) 이 된다.
best case: 한 번에 찾았을 때
// target = 70
// 0 | 10 | 20 | 30 | 40 | 50 | 60 | 70 | 80 | 90 | 100 | 110 | 120 | 130 | 140 |
// 한번에 찾음
이 떄 시간복잡도는 θ(1)이 된다.
binary search에 시간복잡도는?
Ω(1), O(logN) 이렇게 표현 할 수 있다.
case별로 나타내면 아래와 같다.
| – | best | worst | Avg |
|---|---|---|---|
| Ω | Ω(1) | Ω(logN) | |
| O | O(1) | O(logN) | O(logN) |
| θ | θ(1) | θ(logN) |
시간복잡도 속도 비교
O(1) < O(logN) < O(N) < O(N*logN) < O(N^2) < O(2^n) < O(N!) 오른쪽으로 갈수록 느려진다. 즉 성능이 좋지 않다!!
왜 O 표기법을 많이 쓸까?
- 일반적으로 upper bound만 알아도 충분하기 때문에
- 다른 bound를 계산하기 귀찮아서
- 괜히 tight bound로 말했다가 태클 받기 싫어서
- 주위에서 다들 그렇게 쓰니까
- 실은 점근적 표기법의 개념을 잘 모르고