공간복잡도

시간복잡도 & 공간복잡도

등장 배경 코드의 성능, 효율성을 판단할 기준이 필요했다. 실제 실행시간과 메모리 사용량을 측정한다면? 하드웨어의 성능, 소프트웨어(운영체제)의 성능, 호환성 등 외부 요인이 작용하여 동일한 기준으로 비교할 수 없다. 미완성 코드는 실행이 불가능하므로 측정이 불가능하다. → 다른 요인과 무관하게 입력 크기에만 영향을 받는 이론적 시간 측정 방법을 만들었다. 시간복잡도 입력값과 연산 수행 시간의 상관관계를 나타내는 척도이다. 점근 표기법을 이용하여 나타낸다. 💡 점근 표기법이란, 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법을 말한다. 단위 연산의 횟수를 기준으로 계산한다. 💡 단위 연산(primitive operation)이란, 정의, 단순 계산, 비교, 출력 등의 가장 간..