복잡도

복잡도

알고리즘의 복잡도는 입력 크기에 대한 함수로 표기됩니다. 이 함수는 주로 다항식 형태로 나타내며, 알고리즘의 효율성을 나타내는 중요한 지표입니다.

시간 복잡도 (T(n))

시간 복잡도는 알고리즘이 수행하는 기본적인 연산 횟수를 입력 크기에 대한 함수로 표현한 것입니다. 시간 복잡도를 나타내는 방법은 알고리즘이 입력에 대해 얼마나 많은 연산을 수행하는지를 평가하는 데 사용됩니다.

• 기본 연산
  예를 들어, 최댓값 구하기나 팩토리얼 구하기 같은 알고리즘의 시간 복잡도는 T(n)로 나타낼 수 있습니다.
  - 변수 비교, 값 입력, 갱신, 계산 등 단순한 연산들이 해당됩니다.

O(Big O) 표기법

Big O 표기법은 알고리즘의 수행 시간을 간단히 표기하는 방법입니다. 주로 점근적 표기법(Asymptotic Notation)이라고 부르며, 최고차항만을 남기고 나머지 항은 생략합니다.

예를 들어, T(n) = 3n³ + 12n + 6이면 O(n³)로 나타낼 수 있습니다. 이처럼 주요 차수만을 나타내며 상수 항은 생략됩니다.

주요 시간 복잡도

• O(1): 상수 시간
  • 알고리즘의 수행 시간이 입력 크기에 상관없이 일정합니다. 예: 배열의 첫 번째 원소 접근.
• O(log n): 로그 시간
  • 알고리즘이 이진 탐색처럼 반복적으로 문제를 절반씩 줄여가며 해결하는 경우. 예: 이진 탐색.
• O(n): 선형 시간
  • 알고리즘이 입력의 모든 원소를 한 번씩 처리하는 경우. 예: 선형 검색.
• O(n²): 이차 시간
  • 이중 루프를 사용하는 알고리즘의 시간 복잡도. 예: 버블 정렬, 선택 정렬.

공간 복잡도 (Space Complexity)

공간 복잡도는 알고리즘이 실행될 때 사용하는 메모리의 양을 의미합니다. 이는 입력 크기에 따라 프로그램이 얼마나 많은 추가 공간을 필요로 하는지에 대한 분석입니다.

• 고정 공간
  • 프로그램 실행에 항상 필요한 기본적인 메모리 공간. 예: 상수, 함수, 전역 변수 등.
• 가변 공간
  • 입력 크기에 따라 달라지는 공간. 예: 입력 데이터, 리스트, 배열, 재귀 호출 스택 등.

주요 공간 복잡도

• O(1) – 상수 공간 (Constant Space)
  • 입력 크기와 관계없이 일정한 공간만 사용합니다. 예: 변수 몇 개만 사용하는 경우.
• O(log n) – 로그 공간 (Logarithmic Space)
  • 재귀 알고리즘에서 깊이가 log(n)인 경우 발생합니다. 예: 이진 탐색과 같은 알고리즘에서.
• O(n) – 선형 공간 (Linear Space)
  • 입력 크기 n에 비례하여 공간 사용량이 증가합니다. 예: 리스트, 배열, 해시 테이블 등 추가적인 자료구조를 저장할 때.
• O(n²) – 이차 공간 (Quadratic Space)
  • 2차원 배열이나 행렬을 사용하는 경우 공간이 n²만큼 증가합니다. 예: 2차원 배열, 행렬 곱셈 등.