시간복잡도

시간복잡도란 "특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간"이다. 하지만 사용자마다 사양의 차이가 있어 시간을 측정해서 알고리즘을 평가하기에는 어려움이 있기에 시간을 측정하기보단 코드에서 성능에 많은 영향을 주는 부분을 찾아 예측하는것이다.

즉, 시간복잡도는 알고리즘의 효율성을 평가하기 위한 지표 중 하나로, 입력 크기(데이터의 양)가 증가함에 따라 알고리즘의 수행 시간이 어떻게 변하는지를 수학적으로 나타낸 것이다. 시간복잡도는 프로그램의 실행 속도를 예측하고, 성능을 비교할 때 중요한 개념이다.

 

시간복잡도를 나타내는 표기법에는 

최선의 경우인 한번에 찾는 Big- Ω(빅오메가)

최악의 경우인 배열의 길이만큼 걸리는 Big-O(빅오)

평균의 경우인 배열의 길이 중간 만큼 걸리는 Big- Θ(빅세타)

가 있다.

 

보통 Big-O(빅오)와 Big- Θ(빅세타)를 주로 사용하는데 가장 많이사용하는건 Big-O(빅오)이다.

 

시간복잡도의 종류 (Big-O 표기법)

다음은 알고리즘의 시간복잡도를 나타내는 대표적인 Big-O 표기법과 예제이다.

1. O(1) - 상수 시간
   •  설명: 입력 크기와 상관없이 항상 일정한 시간이 소요됨.
   •  예제: 배열에서 특정 인덱스 값 접근 array[i].
   •  특징: 가장 빠르고 효율적.
2. O(log n) - 로그 시간
   •   설명: 입력 크기가 증가할수록 수행 시간이 느리게 증가.
   •   예제: 이진 검색(Binary Search).
   •   특징: 입력 크기가 클수록 효율적.
3. O(n) - 선형 시간
   •   설명: 입력 크기 n에 비례해 수행 시간이 증가.
   •   예제: 배열의 모든 요소를 순회하는 경우 (for-loop).
   •   특징: 크기가 커질수록 실행 시간이 증가.
4. O(n log n) - 로그 선형 시간
   •   설명: 선형과 로그의 결합으로, 일반적으로 효율적인 정렬 알고리즘에서 나타남.
   •   예제: 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort).
   •   특징: 정렬 알고리즘의 평균적인 복잡도.
5. O(n²) - 이차 시간
   •   설명: 입력 크기에 제곱 비례해 수행 시간이 증가.
   •   예제: 중첩된 반복문이 있는 알고리즘 (버블 정렬, 선택 정렬).
   •   특징: 입력 크기가 커지면 매우 비효율적.
6. O(2ⁿ) - 지수 시간
   •   설명: 입력 크기가 증가할 때, 수행 시간이 지수적으로 증가.
   •   예제: 피보나치 수열의 비효율적 재귀 구현.
   •   특징: 매우 비효율적이며, 입력 크기가 작아도 실행 시간이 크게 증가.
7. O(n!) - 팩토리얼 시간
   •   설명: 입력 크기가 증가할수록 수행 시간이 팩토리얼로 증가.
   •   예제: 순열 생성, 외판원 문제(Brute Force 방식).
   •   특징: 극도로 비효율적.

 

시간복잡도 계산 방법

시간복잡도를 계산할 때 주로 사용하는 방법은 다음과 같다:

1. 가장 큰 항만 고려
   •   작은 입력 크기에서는 여러 항이 중요할 수 있지만, 입력 크기 n이 매우 클 경우에는 가장 큰 항이 전체 시간복잡도를 결정한다.
   •   예: T(n) = 3n² + 2n + 1→ 시간복잡도는 O(n²)
2. 상수 계수 무시
   •   상수 계수는 시간복잡도 계산에 영향을 주지 않으므로 무시합니다.
   •   예: T(n) = 5n → 시간복잡도는 O(n)
3. 반복문 분석
   •   반복문의 실행 횟수를 분석하여 시간복잡도를 계산합니다.
   •   단일 반복문: O(n)
   •   중첩 반복문: O(n²), O( n×m ) 등
4. 재귀 함수 분석
   •   재귀 함수는 점화식을 통해 시간복잡도를 계산합니다.
   •   예: 피보나치 재귀 T(n) = T(n−1) + T(n−2) + O(1) → O(2ⁿ)