시간 복잡도(Time Complexity)란
시간 복잡도(Time Complexity)란 알고리즘을 실행하는데 걸리는 시간을 입력 길이의 함수로 정의한 것입니다.
알고리즘의 각 문장을 실행하는데 걸리는 시간을 측정하는 것이 아니라 알고리즘에서 연산의 수가 증가하거나 감소할 때 실행 시간의 변화(증가 또는 감소)에 대한 정보를 제공하는 것입니다.
Big O 표기법으로 시간복잡도 계산하기
시간 복잡도는 입력 길이의 함수로 나타나는 시간입니다. 여기에는 입력 데이터 크기(n)와 시간에 대한 연산 수(N) 사이에 관계가 존재합니다. 이 관계는 시간 복잡도의 성장 속도(Order of growth)로 표기되며, O(n) 형태와 같은 표기법을 사용합니다. 여기서 O는 성장 속도를 나타내고 n은 입력 길이입니다.
Big O 표기법은 알고리즘의 실행 시간을 입력 ‘n’에 대해 얼마나 빠르게 증가하는지 N 개의 연산 수를 기준으로 표현합니다. 따라서 알고리즘의 시간 복잡도는 각 함수 라인에 할당된 모든 O(n)의 조합으로 표기됩니다.
사용되는 시간 복잡도에는 여러 가지 종류가 있습니다. 하나씩 살펴보겠습니다.
- 상수 시간 - O(1)
알고리즘이 입력 크기 n에 의존하지 않을 때 O(1)의 상수 시간 복잡도를 갖는다고 합니다. 입력 크기 n의 여부와 상관없이 실행 시간은 항상 동일합니다.
- 선형 시간 - O(n)
알고리즘의 실행 시간이 입력 길이에 따라 선형적으로 증가하는 경우 선형 시간 복잡도를 갖는다고 합니다. 함수에서 입력 데이터의 모든 값을 검사하는 경우 이러한 O(n)의 시간 복잡도를 가집니다.
- 로그 시간 - O(log n)
알고리즘이 각 단계에서 입력 데이터의 크기를 줄이면 로그 시간 복잡도를 갖는다고 합니다. 이는 연산 횟수가 입력 크기와 같지 않다는 것을 의미합니다. 입력 크기가 증가함에 따라 연산 횟수는 줄어듭니다. 이러한 알고리즘은 이분 트리 또는 이분 검색 함수에서 찾을 수 있습니다. 이는 배열을 두 개로 분할하여 한쪽 부분에서 검색을 시작하여 배열에서 주어진 값을 검색하는 것을 포함합니다. 이를 통해 데이터의 모든 요소에서 작업이 수행되지 않도록 합니다.
- 제곱 시간 - O(n²)
알고리즘이 실행 시간이 입력 길이의 제곱에 따라 비선형적으로 증가하는 경우 (n²) 비선형 시간 복잡도를 갖는다고 합니다. 일반적으로 중첩 루프는 이러한 O(n²) 시간 복잡도를 가집니다. 여기서 한 루프는 O(n)을 사용하며 함수에 루프 안에 루프가 포함되어 있으면 O(n) * O(n) = O(n²)의 시간 복잡도를 갖게 됩니다.
마찬가지로 함수에 ‘m’개의 루프가 정의되어 있으면 시간 복잡도는 O(n ^ m)으로 표기되며 이를 다항 시간 복잡도 함수라고 합니다.
빅오 표기법으로 시간 복잡도를 계산하는 방법은 다음과 같습니다.
- 순서 (Order): 입력 크기가 n일 때 알고리즘의 실행 시간이 f(n)과 동일한 성장률을 보이는 경우, 알고리즘의 시간 복잡도는 O(f(n))으로 표기됩니다.
- 상수 계수 및 낮은 차수 항 무시: 빅오 표기법에서는 상수 계수와 입력 크기 n보다 차수가 낮은 항을 무시합니다. 예를 들어, 2n^2 + 3n + 1은 O(n^2)로 표기됩니다.
- 최악의 경우 분석: 빅오 표기법은 알고리즘의 최악의 경우 실행 시간을 나타냅니다. 즉, 모든 입력 데이터에 대해 가장 느린 실행 시간을 고려합니다.
시간복잡도 표기법 종류
1. 오메가 표기법 (Ω)
- 최악의 경우 실행 시간의 하한을 나타냅니다.
- 입력 크기가 n일 때 알고리즘의 실행 시간이 f(n)보다 빠르지 않음을 의미합니다.
- 예시: Ω(n^2)는 입력 크기가 커질수록 실행 시간이 n^2보다 느리지 않음을 의미합니다.
2. 세타 표기법 (Θ)
- 알고리즘의 실행 시간의 점근적 성장률을 나타냅니다.
- 입력 크기가 n일 때 알고리즘의 실행 시간이 f(n)과 동일하다는 것을 의미합니다.
- 예시: Θ(n log n)은 입력 크기가 커질수록 실행 시간이 n log n과 동일하게 증가한다는 것을 의미합니다.
3. 소오 표기법 (o)
- 최악의 경우 실행 시간의 상한을 나타냅니다.
- 입력 크기가 n일 때 알고리즘의 실행 시간이 f(n)보다 빠르다는 것을 의미합니다.
- 예시: o(n^2)는 입력 크기가 커질수록 실행 시간이 n^2보다 빠르게 증가한다는 것을 의미합니다.
4. 소오메가 표기법 (ω)
- 최악의 경우 실행 시간의 상한과 하한을 동시에 나타냅니다.
- 입력 크기가 n일 때 알고리즘의 실행 시간이 f(n)보다 빠르고 g(n)보다 느리다는 것을 의미합니다.
- 예시: ω(n) ∩ o(n^2)는 입력 크기가 커질수록 실행 시간이 n보다 빠르고 n^2보다 느리다는 것을 의미합니다.
5. 틸다 표기법 (~)
- 평균 실행 시간을 나타냅니다.
- 입력 크기가 n일 때 알고리즘의 평균 실행 시간이 f(n)에 가까워진다는 것을 의미합니다.
- 예시: ~n log n은 입력 크기가 커질수록 평균 실행 시간이 n log n에 가까워진다는 것을 의미합니다.
6. 확률적 시간 복잡도
- 알고리즘의 실행 시간이 입력에 따라 확률적으로 변하는 경우 사용합니다.
- 예시: O(1) with probability 1/2는 알고리즘이 50% 확률로 1 단계에서 실행되고 50% 확률로 다른 실행 시간을 가질 수 있음을 의미합니다.
시간 복잡도 계산하는 예시
public void test(List<Integer> nums) {
calls(nums);
}위 test 함수의 시간복잡도는 무엇일까요? 정답은 calls 함수에 따라 달라지기 때문에, 알 수 없습니다.
public void test(List<Integer> nums) {
calls(nums);
}
public void calls(List<Integer> nums) {
return;
}그렇다면 위 처럼 calls 함수가 구현되어 있다면, test 함수의 시간복잡도는 O(1)이 됩니다.calls 함수는 아무것도 하지 않고 상수 시간에 끝나기 때문입니다.
public void test(List<Integer> nums) {
calls(nums);
}
public void calls(List<Integer> nums) {
for (Integer num : nums) {
System.out.println(num);
}
}위 코드에서는 calls 메서드는 파라미터로 받은 리스트의 데이터를 순차적으로 접근해 정수를 출력합니다.
내부적으로는 각 데이터를 상수 시간에 처리하여 시간 복잡도가 O(1)이 되지만, 전체적으로 리스트를 n번 호출하므로 시간 복잡도는 O(n)이 되죠.
public void test(List<Integer> nums) {
for (Integer num : nums) {
calls(nums);
}
}
public void calls(List<Integer> nums) {
for (Integer num : nums) {
System.out.println(num);
}
}위 코드에서는 O(n)시간이 걸리는 calls를 for 루프를 순회하면서 nums 만큼 호출하므로,
O(n) x n = O(n^2)의 시간 복잡도가 소요됩니다.
면접에서 시간 복잡도를 물어보는 이유
시간 복잡도를 물어보는 이유는 실무에서 코드의 성능과 서비스 품질에 영향을 미치게됩니다.
시간 복잡도를 고려하며 개발하는 개발자가 자연스럽게 성능 좋은 코드를 작성할 수 있기 때문이죠.
시간 복잡도를 고려하여 개발하면 좋은 습관처럼 몸에 배워져 향후 코드 품질이 향상될 수 있습니다.
기술 면접에서는 코드를 통해 시간 복잡도를 물어보거나, 코딩 테스트를 통해 확인하는 추세입니다.
Sorting 별 시간 복잡도
코딩 테스트
- 코딩 테스트에서는 최악의 케이스인 빅-오 표기법을 기준으로 생각해야 합니다.
- 시간 제한 1초는 1억번의 연산내에 문제를 해결해야 한다는 것으로 생각하면 됩니다.
- 연산 횟수 = 시간복잡도 x 데이터의 크기 입니다.
참고
'ComputerScience > ComputerScience' 카테고리의 다른 글
| 한글코드 관련 자료조사, KS 완성형, 유니코드, UTF 인코딩 등 (0) | 2023.09.08 |
|---|
