[EXP 24.08.30] 시간 복잡도와 공간 복잡도

코드 분석 결과 및 시간, 공간 복잡도를 설명한 리포트

 

시간 복잡도 (Time Complexity)

: 입력되는 n의 크기에 따라 실행되는 조작의 수

• 즉, 알고리즘의 성능
• 실행 환경에 따라 실행 시간이 달라질 수 있으므로, 실제 시간보다는 명령문의 실행 빈도수를 계산하여 실행 시간을 구함
• 주로 Big-O 표기법을 사용

Big-O 표기법

: 입력 크기 n에 따라 알고리즘의 실행 시간이 어떻게 변화하는지를 나타낸다.

 

🔥 𝑂(1) < 𝑂(log n) < 𝑂(n) < 𝑂(nlog n) < 𝑂(n^2) < 𝑂(n^3) < 𝑂(2^n) < 𝑂(n!)

 

1. 상수 시간 (O(1))

• 입력 크기와 관계없이 일정한 시간이 소요된다.
• 예시: 배열의 특정 인덱스에 접근하기, 스택의 push 및 pop 연산.

2. 로그 시간 (O(log n))

• 입력 크기에 대해 로그 함수처럼 증가하는 시간복잡도이다. 일반적으로 이진 검색 알고리즘에서 나타난다.
• 예시: 이진 탐색, 이진 탐색 트리에서의 검색.

3. 선형 시간 (O(n))

• 입력 크기 n에 비례하여 시간이 증가한다.
• 예시: 배열의 모든 원소를 순회하기, 단일 루프.

4. 선형 로그 시간 (O(n log n))

• 입력 크기와 로그 함수의 곱으로 증가하는 시간복잡도이다. 주로 효율적인 정렬 알고리즘에서 사용된다.
• 예시: 합병 정렬 (Merge Sort), 퀵 정렬 (Quick Sort) 평균 경우.

5. 이차 시간 (O(n^2))

• 입력 크기 n의 제곱에 비례하여 시간이 증가한다. 보통 중첩 루프에서 나타난다.
• 예시: 버블 정렬 (Bubble Sort), 선택 정렬 (Selection Sort), 삽입 정렬 (Insertion Sort).

6. 삼차 시간 (O(n^3))

• 입력 크기 n의 세 제곱에 비례하여 시간이 증가한다. 주로 세 개의 중첩 루프에서 나타난다.
• 예시: 특정 그래프 알고리즘, 삼중 루프를 가진 계산.

7. 지수 시간 (O(2^n))

• 입력 크기 n에 대한 지수 함수처럼 시간이 증가한다. 매우 비효율적이다.
• 예시: 부분 집합 생성, 재귀적 해결 방법 (예: 피보나치 수 계산의 간단한 재귀 방법).

8. 팩토리얼 시간 (O(n!))

• 입력 크기 n의 팩토리얼에 비례하여 시간이 증가한다. 매우 비효율적이며, 주로 모든 경우의 수를 고려하는 문제에서 발생한다.
• 예시: 순열 생성, 특정 그래프 문제의 모든 가능한 해를 탐색하는 알고리즘.

 

백준 시간복잡도 문제 이해하기

https://www.notion.so/goormkdx/86bbd1261c264ebe886629a3f3716ebb?v=2b47bffe11354519be26192577e17ce7&pvs=4

백준 시간복잡도 | Notion

 

---

 

공간 복잡도 (Space Complexity)

: 알고리즘이 실행되는 동안 필요로 하는 메모리 공간의 양을 측정하는 척도

• 입력 크기 n에 따라 알고리즘이 사용하는 메모리 공간이 어떻게 변화하는지를 나타낸다.
• 공간 복잡도는 보조공간(Auxiliary Space)과 입력 공간(input size)을 합친 포괄적인 개념이다.
• 시간과 공간은 반비례적 경향이 있음
• 최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선

알고리즘에 필요한 공간

1. 고정 공간 (Fixed Space)
   • 알고리즘 실행 전, 알고리즘에 의해 사용될 공간의 총량. 변수, 상수, 데이터 구조 등이 포함된다.
   • 예시: 정수 변수, 고정 크기의 배열.
2. 가변 공간 (Variable Space)
   • 알고리즘 실행 중에 동적으로 할당되는 메모리 공간. 함수 호출 시의 스택 공간, 동적 메모리 할당 등이 포함된다.
   • 예시: 재귀 호출 스택, 동적으로 할당된 배열 또는 리스트.

주요 공간 복잡도

1. 상수 공간 (O(1))
   • 입력 크기와 관계없이 일정한 메모리 공간을 사용하는 경우.
   • 예시: 단일 변수, 고정 크기의 배열.
2. 선형 공간 (O(n))
   • 입력 크기 n에 비례하여 메모리 공간이 증가하는 경우.
   • 예시: 입력 크기와 같은 크기의 배열을 사용하는 경우, 링크드 리스트.
3. 이차 공간 (O(n^2))
   • 입력 크기 n의 제곱에 비례하여 메모리 공간이 증가하는 경우.
   • 예시: 이차원 배열, 특정 그래프 알고리즘에서의 메모리 사용.

공간복잡도 분석 방법

1. 고정 공간 분석
   • 알고리즘에서 사용하는 고정된 메모리 공간을 분석한다. 변수, 상수, 고정 크기 배열 등이 포함된다.
   • 예시: 변수 5개, 고정 크기 배열 100개.
2. 가변 공간 분석
   • 알고리즘 실행 중에 동적으로 할당되는 메모리의 양을 분석한다. 재귀 호출 시의 스택 공간, 동적 메모리 할당 등이 포함된다.
   • 예시: 재귀 깊이에 따른 스택 공간, 동적 리스트의 크기.
3. 최악의 경우 분석
   • 입력 크기 n가 커질 때, 알고리즘이 필요로 하는 최대 메모리 양을 분석한다.
   • 예시: 알고리즘이 최악의 경우 n2의 공간을 필요로 하는 경우.

공간복잡도 측정 시 고려사항

• 데이터 구조: 알고리즘이 사용하는 데이터 구조의 메모리 요구량.
• 재귀 호출: 재귀 알고리즘의 경우, 호출 스택의 메모리 사용량.
• 동적 할당: 동적으로 할당되는 메모리의 양.

 

정렬 알고리즘 비교

 

자료구조 비교