TIL79-01 면접준비03: 시간복잡도와 공간복잡도

시간복잡도와 공간복잡도

• 시간 복잡도는 알고리즘의 실행 시간, 공간 복잡도는 메모리 사용량을 나타내며, 빅 오 표기법을 이용하여 표현한다. 효율적인 알고리즘은 시간/공간 복잡도가 낮으며, 때로 둘 중 하나를 포기해야 할 수도 있다.

  • 시간 복잡도는 알고리즘의 실행 시간을 입력 크기의 함수로 설명하는 것이며, 공간 복잡도는 알고리즘이 해결하는 문제의 메모리 사용량을 설명합니다. 이 두 가지 요소는 컴퓨터 알고리즘의 효율성을 판단하는 데 중요한 역할을 합니다.
  • 빅 오 표기법을 사용하여 두 요소를 나타낼 수 있으며, 이것은 알고리즘의 실행 시간과 메모리 사용 상한 값을 제공합니다.
  • 일반적으로 시간 복잡도와 공간 복잡도가 낮은 알고리즘이 더 효율적이며, 더 큰 입력을 처리할 수 있습니다. 그러나 때로는 시간 복잡도와 공간 복잡도 사이에 상충관계가 있을 수 있으며, 이러한 경우 하나를 포기해야 할 수도 있습니다.

빅 오 표기법

• 빅 오 표기법은 알고리즘의 성능을 비교하거나 최적화하는 데 유용하며, 일반적으로 빅 오 표기법이 낮은 알고리즘이 더 효율적입니다.

  • 알고리즘의 입력 크기가 n일 때, 빅 오 표기법은 알고리즘의 실행 시간 또는 메모리 사용량이 n에 대한 상한 값을 나타내는 수식으로 표현됩니다. 이 때, 가장 영향력 있는 항을 선택하여 표현합니다.
  • 예를 들어, 알고리즘의 시간 복잡도가 O(n^2)이라면, 입력 크기가 n일 때 알고리즘의 실행 시간이 n^2에 비례한다는 것을 의미합니다. 따라서 입력 크기가 증가할수록 실행 시간이 매우 빠르게 증가합니다. 반면, 시간 복잡도가 O(log n)이라면, 입력 크기가 증가할수록 실행 시간이 더 느리게 증가합니다.