영상 내용을 글로도 정리했습니다
예제로 알아보는 시간 복잡도(time complexity) 개념
아래와 같은 코드가 있습니다. 이 코드는 정수 타입의 배열 inputs과 multiplier를 파라미터로 받습니다.
내부적으로 어떻게 동작하는지 살펴보면, inputs에 있는 모든 정수들을 mutiplier로 곱해줘서 그 결과를 새로운 정수 타입의 배열인 nums에 담아 최종적으로 그 nums를 반환하고 있습니다.
int[] multiply(int[] inputs, int multiplier) {
int[] nums = new int[inputs.length];
for (int i = 0 ; i < inputs.length ; i++) {
nums[i] = inputs[i] * multiplier;
}
return nums;
}
이 함수의 성능이 궁금합니다.
이 함수의 실행 시간(running time)은 어느 정도일까요?
이 함수의 실행 시간을 표현하려면 어떻게 해야 할까요?
1. 실행 시간 계산 단순화를 위해 필요한 사전 작업
우선 실행 시간 계산을 위해 몇 가지 단순화시켜야 할 것이 있습니다.
- 실행 시간의 개념을 (흔히 우리가 알고 있는 그런 시간적인 개념이 아니라) '함수나 알고리즘 수행에 필요한 스텝(step) 수'라고 정의하도록 하겠습니다. 왜냐하면 컴퓨터마다 성능이 다르기 때문에 실행 시간을 밀리초(milliseconds)나 초(seconds) 단위로 표현하는 것은 어려울 것 같기 때문입니다.
- 이때 '스텝 수는 각 코드 라인마다 고정적으로 정해져 있다(constant)'고 하겠습니다.
2. 실행 시간을 나타내는 함수 T(N) 구하기
이렇게 계산하기 쉽게 단순화시킨 후에 위의 코드를 코드 라인별로 분석하면 아래와 같습니다.
각 라인 별로 수행되는 cost(스텝 수)는 각각 c1, c2, c3, c4 이렇게 상수로 정해놓고 각 라인이 실행되는 횟수를 구해보면, 배열의 input size가 N이라고 했을 때 각각1, N+1, N, 1 이 되겠습니다. 여기서 N+1의 경우 왜 1이 더해졌냐면 루프를 돌면 마지막으로 루프 탈출을 위해 한번 더 검사하기 때문에 그렇습니다.
이제 이 상황에서 전체 실행 시간을 input size N에 대한 함수로 표현하면
T(N) = c1 + c2*(N+1) + c3*N + 1
= (c2 + c3)*N + (c1 + c2 + 1)
= a*N + b
가 됩니다. 마지막 줄의 a는 (c2 + c3)를 치환한 것이고 b는 (c1 + c2 + 1)를 치환한 것이라고 보면 되겠습니다.
3. N → ∞ 일 때 T(N)이 어떻게 될지 분석하기
이 상황에서 몇 가지 생각해볼 부분이 있습니다.
- 우선 'T(N) = a*N + b' 이상으로 더 구체적으로 계산하기는 어렵다는 점이 있고요
- N이 작을 땐 실행 시간이 큰 의미가 없다는 점이죠. 어차피 매우 빨리 끝날 테니까요.
그렇다면 우리가 집중해야 할 부분은 N → ∞ 일 때의 실행 시간입니다. 즉, input size N이 무한대를 향해 계속 증가하게 된다면, 이 함수의 실행 시간은 어떻게 될까요?
이를 단순하게 표현하기 위해 몇 가지 작업을 해줍시다. N → ∞ 일 때 T(N)에서 덜 중요한 것은 제거를 해주는 것이죠.
- 우선 최고차항만 제외하고 나머지 항들은 모두 제거해 줍니다. 왜냐하면 N이 커지면 커질수록 최고차항을 제외한 나머지 항들의 영향력은 상대적으로 미미해지기 때문입니다. 지금 예에서는 상수항인 b를 제거해줍니다.
- 그리고 최고차항의 계수도 제거해 줍시다. 마찬가지의 이유로 N → ∞ 인 상황이기 때문에 계수도 큰 의미가 없기 때문입니다.
이렇게 했을 때 최종적으로 남는 것은 N이 되고 이를 표기하면
𝚹(N)
이 됩니다. (𝚹(big theta)인데 저는 편의상 theta라고 하겠습니다)
여기서 𝚹가 의미하는 것은 이후 내용을 보시면 이해하실 수 있습니다.
점근적 분석 & 점근적 표기법
우리가 앞에서 N → ∞일 때 T(N)의 최고차항을 제외하고는 다 제거해주는 것과, 최고차항에서도 계수는 제거해서 N이 무한대를 향해 커질 때 어떤 단순한 형태로 접근하는지 분석을 했는데, 이런 분석 방식을 점근적 분석(asymptotic analysis)이라고 합니다.
즉, 점근적 분석이란 N이 계속 커질 때 함수 T(N)이 어떤 형태의 함수로 근사(혹은 접근)하게 되는지를 분석하는 방식입니다. 우리는 이 방식을 함수의 실행 시간을 단순화할 때 사용하는 것이죠.
그리고 점근적 분석을 통해 근사된 함수를 𝚹(N)로 표기하는 것을 점근적 표기법(asymptotic notation)이라고 합니다.
시간 복잡도(time complexity)란?
- 함수나 알고리즘에서 시간 복잡도(time complexity)의 개념은 '함수의 실행 시간을 표현하는 것'을 의미합니다.
- 이때 주로 '점근적 분석을 통해 실행 시간을 단순하게 점근적 표기법으로 표현한다'라고 이해하시면 되겠습니다.
그러므로 이제 우리는 함수나 알고리즘의 시간 복잡도를 계산할 때 점근적 분석에 근거하여 input size에 최고차항이 어떻게 될지에 집중하면 되겠습니다.
예제로 알아보는 점근적 표기법(asymptotic notation)
점근적 표기법을 자세히 알아보겠습니다.
boolean exists(int[] inputs, int target) {
for (int i = 0 ; i < inputs.length ; i++) {
if (inputs[i] == target) {
return true;
}
}
return false;
}
위 코드는 정수 타입의 배열 inputs에서 찾으려는 정수 target이 있으면 true를 반환하고 없으면 false를 반환하는 함수입니다. 루프를 돌면서 inputs에 있는 모든 정수들을 앞에서부터 차례대로 확인하다가 찾는 target을 발견하게 되면 바로 return true를 하는 것이죠.
상황에 따라 실행 시간이 달라지는 함수의 시간 복잡도는?
이 함수의 시간 복잡도를 구하려고 하니, 앞전의 함수와는 다르게 고려할 사항이 생겼습니다. target을 찾으면 바로 함수가 종료되기 때문에, 배열의 어느 위치에 target이 있는지에 따라 함수의 실행 시간이 차이가 나기 때문입니다.
1. 최선과 최악의 상황으로 구분해보자
그래서 best case와 worst case로 나눠서 실행 시간이 어떻게 되는지 확인해보기로 했습니다.
아래 이미지에서 정리한 것처럼 best case는 맨 처음에 찾는 target이 있는 경우입니다. 이 때는 한 번의 확인으로 바로 함수는 true를 반환하고 종료되기 때문에 input size N과 상관없이 아주 빠르게 상수(constant) 시간으로 종료가 됩니다.
반면에 worst case는 찾는 target이 배열의 맨 마지막에 있거나, 아예 없는 경우입니다. 이 때는 배열에 있는 모든 정수들을 확인해야 하기 때문에 총 N번의 확인을 하게 되죠. 즉 worst case의 경우에는 실행 시간이 input size N에 비례한다고 볼 수 있겠습니다.
2. 시간 복잡도를 서술하는 두 가지 방법
그러면 이런 특징을 바탕으로 이 함수의 실행 시간을 문장으로 서술해보면 어떻게 될까요? 두 종류의 서술이 가능할 것 같습니다.
- 하한선(lower bound)을 기준으로 서술 : 함수 실행 시간은 아무리 빨라도 상수 시간 이상입니다
- 상한선(upper bound)을 기준으로 서술 : 함수 실행 시간은 아무리 오래 걸려도 input size N에 비례하는 정도 이하입니다
3. 시간 복잡도를 표기하는 두 가지 방법
그리고 이렇게 문장으로 서술된 내용을 기호로 표기하면 각각 아래와 같습니다.
- 𝝮(1)
- O(N)
여기서 𝝮(big omega)는 lower bound를 의미하고요, O(big Oh)는 upper bound를 의미합니다. 𝝮(1)의 1이 의미하는 것은 상수(constant)를 의미합니다. 즉 input size N과 상관없이 N이 크던 작던 상수라는 의미이고요, O(N)의 N이 의미하는 것은 input size N에 비례하는형태를 의미합니다.
정리하면 이렇습니다. 이 함수의 시간 복잡도는
𝝮(1)
라고도 할 수 있고
O(N)
라고도 할 수 있습니다.
보통 일반적으로 하한선보다는 상한선을 더 궁금해하기 때문에 주로 O(N)을 많이 쓴다고 볼 수 있겠습니다.
이번에는 case별로 구분해서 시간 복잡도를 구해보겠습니다.
1. Best case
아래 이미지에서 Best case는 배열의 맨 처음 정수가 찾으려던 target과 같은 경우를 의미하는데, 이 경우에는 실행 시간의 lower bound와 upper bound 모두 상수 시간입니다. 그래서 둘 다 𝝮(1)과 O(1)으로 표현할 수 있습니다.
지금처럼 이렇게 lower bound와 upper bound가 같은 함수 형태를 띠게 되면 lower bound와 upper bound가 같기 때문에, 매우 tight 한 형태의 bound임을 알 수 있습니다. 즉 best case에서 실행 시간은 항상 상수 시간인 건데요, 이런 경우에는 실행 시간을 𝚹(1)로 표현할 수 있습니다.
즉, 𝚹는 tight bound를 의미하며, lower bound와 upper bound가 같은 함수 형태를 나타낸다면, 한 번에 tight bound인 𝚹로 표기할 수 있습니다.
2. worst case
이번엔 worst case를 살펴보겠습니다. 앞에서 살펴봤던 것처럼 worst case는 찾으려는 target이 맨 마지막에 있거나 아예 없는 경우인데, 이 case에서의 실행시간은 lower bound와 upper bound가 모두 input size N에 비례하는 형태입니다. 그래서 둘 다 𝝮(N)과 O(N)으로 표기할 수 있습니다.
마찬가지로 이 case에서도 lower bound와 upper bound가 같은 형태를 띠게 되기 때문에 tight bound에 해당하고, 이 경우에 실행 시간을 𝚹(N)으로 표현할 수 있습니다.
3. average case
마지막으로 best case도 아니고 worst case도 아닌 경우를 average case라고 합니다. 일반적인 경우를 의미하는 것인데요, average case를 어떻게 볼 것인지가 좀 애매한데, 위 경우에는 중간 정도에서 target을 찾는 것을 average case라고 퉁칠 수 있을 것 같습니다. 그 경우 시간 복잡도는 N/2의 형태가 될 것이고, 점근적 분석에 따라 계수를 제거하고 표시하면 O(N)이라고 볼 수 있겠습니다.
average case의 upper bound는 O(N)으로 확실한데 lower bound를 어떻게 봐야 할지 애매하기 때문에, 저는 average case를 O(N)으로만 표기하도록 하겠습니다.
최종적으로 이 함수를 case에 따라 시간 복잡도를 표기하면 아래 이미지와 같습니다.
아래 표는 점근적 표기법과 case를 정리한 내용입니다.
가끔 블로그나 문서를 보면 best case의 시간 복잡도는 항상 𝝮로 표기를 하고, average cae는 O로, worst case는 𝚹로 표기하는 것을 볼 수 있는데요, 그건 적절한 사용은 아닌 것 같고요, case에 따라 점근적 표기법은 무엇이든 적절하게 사용할 수 있다고 보시면 되겠습니다.
주요 시간 복잡도의 실행 시간 속도 비교
마지막으로 대표적인 시간 복잡도를 빠른 순서부터 나열하면 아래와 같습니다. 오른쪽으로 갈수록 더 오래 걸린다고 이해하시면 되십니다.
O(1) < O(logN) < O(N) < O(N*logN) < O(N^2) < O(2^N) < O(N!)
