시간복잡도와 공간복잡도

Big-O 표기법?

-알고리즘 성능을 수학적으로 표기해주는 표기법

-알고리즘의 시간복잡도(필요한 시간)와 공간복잡도(필요한 메모리)를 표현할 수 있게 해줌

-알고리즘의 실제 러닝 타임을 표시한다기 보다 데이터나 사용자의 증가율에 따른 알고리즘의 성능 예측이 목표

---

 

Big-O의 시간복잡도 관련 표기법

• O(1): 입력 크기에 관계없이 알고리즘의 수행 시간이 일정한 상수 시간을 가지는 것을 나타냅니다. (예: 배열에서 인덱스를 사용하여 특정 값을 찾는 경우)
• O(log n): 입력 크기가 늘어날 때마다 수행 시간이 로그 함수의 증가율로 증가하는 것을 나타냅니다. (예: 이진 검색 알고리즘)
• O(n): 입력 크기에 비례하여 알고리즘의 수행 시간이 증가하는 것을 나타냅니다. (예: 배열에서 최대값을 찾는 경우)
• O(n log n): 입력 크기가 늘어날 때마다 수행 시간이 n과 로그 n의 곱으로 증가하는 것을 나타냅니다. (예: 병합 정렬 알고리즘)
• O(n^2): 입력 크기의 제곱에 비례하여 알고리즘의 수행 시간이 증가하는 것을 나타냅니다. (예: 버블 정렬 알고리즘)
• O(2^n): 입력 크기가 1 증가할 때마다 수행 시간이 2배

Big-O의 공간복잡도 관련 표기법

• O(1): 알고리즘이 고정된 메모리 양을 사용하는 경우 (예: 상수 개수의 변수를 사용하는 경우)
• O(n): 알고리즘이 입력 크기와 비례하는 메모리 양을 사용하는 경우 (예: 입력 배열을 저장하는 경우)
• O(n^2): 알고리즘이 입력 크기의 제곱과 비례하는 메모리 양을 사용하는 경우 (예: 2차원 배열을 사용하는 경우)
• O(log n): 알고리즘이 입력 크기에 로그 함수의 증가율과 비례하는 메모리 양을 사용하는 경우 (예: 이진 트리를 사용하는 경우)

---

그러나 실제로는 Big-O를 사용하여 알고리즘의 성능을 평가하기보다는 실제로 알고리즘을 실행하여 성능을 측정하는 것이 더욱 정확하다.

 

---

로그 함수는 어떤 수를 다른 수의 거듭제곱으로 나타내는 함수입니다. 예를 들어, 2를 몇 번 거듭제곱해야 8이 되는지를 구할 때, log₂ 8을 계산하면 됩니다. 이 때, 밑이 2인 로그 함수를 사용한 것입니다.