복잡도

면접 예상 질문

1. 시간복잡도와 공간복잡도가 무엇인가요?

시간(T)과 입력값(input size, N)의 관계를 나타낸 것을 시간 복잡도라고 합니다.

공간복잡도는 프로그램을 실행했을 때 필요로 하는 자원 공간의 양을 의미합니다. 정적으로 선언된 변수 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 하는 경우도 포함됩니다.

2. Big-O표기법 (빅오표기법) 이란 무엇인가요?

빅오 표기법은 복잡한 시간 복잡도를 간단히 표기하기 위해 최고 차수만 이용해 표기한 것을 말합니다.

Big -O는 시간 복잡도를 간단히 나타낼 수 있는 점근 표기법 중 하나로 시간 복잡도와 마찬가지로 가로축은 N, 세로축은 T을 나타내는 그래프로 표기할 수 있습니다.

3. 시간 복잡도는 왜 필요할까요?

시간 복잡도는 알고리즘이 문제를 해결하는 데 걸리는 시간의 측정이며, 알고리즘의 효율성을 분석하는 도구입니다. 알고리즘은 주어진 입력에 대해 문제를 해결하는 방법을 설명한 것이며, 같은 문제를 해결하는 다양한 알고리즘이 존재할 수 있습니다.