시간복잡도와 공간복잡도

시간복잡도와 공간복잡도

시간복잡도와 공간복잡도는 알고리즘의 성능을 측정하는데 사용되는 개념

 

시간복잡도

시간복잡도는 알고리즘이 문제를 해결하는 데 걸리는 시간을 나타내는 것으로, 입력 크기에 따라 알고리즘의 수행 시간이 어떻게 증가하는지 분석합니다. 

일반적으로 알고리즘의 최악의 경우 시간복잡도를 사용합니다.

시간복잡도는 주로 빅오 표기법(Big O notation)으로 표시되며, 입력 크기 n에 대한 알고리즘의 실행 시간이 O(f(n))으로 표기됩니다.

여기서 f(n)은 n의 함수이며, 상수값은 생략됩니다.

예를 들어, O(n)은 입력 크기 n에 대해 선형적으로 증가하는 시간복잡도를 의미합니다.

O(n^2)은 입력 크기 n의 제곱에 비례하는 시간복잡도를 의미합니다.

공간복잡도

공간복잡도는 알고리즘이 문제를 해결하는 데 필요한 메모리 공간의 양을 나타내는 것으로, 입력 크기에 따라 알고리즘의 메모리 사용량이 어떻게 증가하는지 분석합니다.

공간복잡도도 빅오 표기법으로 표시됩니다.

입력 크기 n에 대한 알고리즘의 공간복잡도가 O(g(n))으로 표기되면, 알고리즘의 실행에 필요한 메모리 사용량이 g(n)의 상수 배 이하로 증가함을 의미합니다.

예를 들어, O(1)은 공간복잡도가 입력 크기에 관계없이 일정한 것을 의미합니다.

O(n)은 입력 크기에 비례하여 메모리 사용량이 증가함을 의미합니다.