시간 복잡도(Time Complexity) 란?

알고리즘의 성능을 측정하는데 사용되는 중요한 개념. 이는 입력 크기에 따라 알고리즘이 실행되는 시간의 양을 나타냄. 시간 복잡도는 주로 Big - O 표기법을 사용하여 표현됨.
Big - O 표기법은 알고리즘의 최악의 경우 성능을 나타내며, 가장 중요한 요소에 따라 실행 시간을 추정

Big - O 표기법의 주요 유형

1. O(1) - 상수 시간(Constant Time)
   -입력 크기에 상관없이 항상 일정한 시간이 걸리는 알고리즘
   ex) 배열의 특정 인덱스에 접근하는 경우

2. O(log n) - 로그 시간(Logarithmic Time)
   -입력 크기가 증가할 때마다 실행 시간이 로그의 형태로 증가하는 알고리즘
   ex) 이진탐색

3. O(n) - 선형 시간(Linear Time)
   -입력 크기가 증가함에 따라 실행 시간이 선형 로그 형태로 증가하는 알고리즘
   ex) 배열의 모든 요소를 한 번씩 순회하는 경우

4. O(n log n) - 선형 로그 시간(Linearithmic Time)
   -입력 크기가 증가함에 따라 실행 시간이 선형 로그 형태로 증가하는 알고리즘
   ex) 병합 정렬, 퀵 정렬(평균인 경우)

5. O(n^2) - 이차 시간(Quadratic Time)
   -입력 크기에 제곱에 비례하여 실행 시간이 증가하는 알고리즘
   ex) 버블 정렬, 삽입 정렬, 선택 정렬

6. O(2^n) - 지수 시간(Exponential Time)
   -입력 크기가 증가할 때마다 실행 시간이 지수 형태로 증가하는 알고리즘
   ex) 피보나치 수열을 재귀적으로 계산하는 알고리즘(비효율적 방식)

7. O(n!) - 팩토리얼 시간(Factorial Time)
   -입력 크기 n에 대해 n!(n 팩토리얼) 만큼의 시간이 소요되는 알고리즘
   ex) 순열 생성 알고리즘

어떤 알고리즘이 더 좋은가?

• 상수 시간(O(1)) 은 입력 크기에 관계없이 일정한 시간이 걸리므로 항상 가장 빠름
• 로그 시간(O(log n)) 은 큰 입력 크기에 대해 효율적임
• 선형 시간(O(n)) 은 입력 크기에 비례하여 시간이 증가하지만, 큰 입력 크기에 대해서도 여전히 비교적 효율적임
• 선형 로그 시간(O(n log n)) 은 정렬과 같은 문제에서 매우 효율적
• 이차 시간(O(n^2)) 은 작은 입력 크기에서 사용 가능하지만, 큰 입력 크기에서는 비효율적임
• 지수 시간(O(2^n)) 과 팩토리얼 시간(O(n!)) 은 대부분의 현실적인 문제에서 사용할 수 없음