시간복잡도, 공간복잡도

✅ 시간 복잡도

시간 복잡도는 알고리즘이 입력 크기의 함수로 실행되는데 걸리는 시간입니다. ex) 알고리즘이 n개의 요소를 정렬하는데 n단계를 거치면 시간 복잡도는 O(n)입니다. 시간 복잡도를 계산하기 위해서는 알고리즘이 입력 크기의 함수로 수행하는 기본 연산의 수를 세어야 합니다. 표기법 O(n)은 알고리즘의 실행 시간이 n에 비례하거나 어떤 상수 인수의 최대 n배에 비례함을 의미하며 이를 빅오 표기법이라 합니다. 시간 복잡도는 서로 다른 알고리즘을 비교하고 주어진 문제에 가장 적합한 알고리즘을 선택하는데 도움이 됩니다.

✅ 공간 복잡도

공간 복잡도는 알고리즘이 입력 크기의 함수로 사용하는 메모리의 양입니다. ex) 알고리즘이 n개의 요소를 저장하기 위해 n비트의 공간이 필요한 경우 공간 복잡도도 O(n)입니다. 공간 복잡성은 알고리즘에 필요한 메모리 양과 사용 가능한 리소스에 맞는지 여부를 평가하는 데 도움이 됩니다.

🤔 알아야하는이유?

시간복잡도, 공간복잡도는 알고리즘 문제를 해결할 때 중요한 개념입니다. 문제를 해결하는데 얼마나 걸리는지, 얼만큼의 메모리를 효율적으로 사용하는지를 나타내는 지표입니다. 어떠한 방법이 가장 적합하다라는 질문에는 처음부터 답하기 어렵지만 요구사항에 맞지 않는 알고리즘은 걸러낼 수 있습니다. 이는 불필요한 시간 투자를 막기 위한 사전점검으로 생각되며 문제를 풀기전에 필수적으로 해야 한다고 생각합니다.