📋시간복잡도

'입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는 가?'

시간 복잡도 쉽게 예측하는 법

재귀 함수

재귀 함수의 Main Logic * 반복 횟수

• 반복횟수
  • 1회 호출 시 n번 반복을 총 m번 수행 -> n^m
  • 1회 호출 시 3번 추가 호출 -> 3^n

📋공간복잡도

'입력 크기에 대해 어떠한 알고리즘이 실행되는데 필요한 메모리 공간의 양'

📌TIP
보통 공간복잡도를 측정할 때 재귀함수의 함수 호출에 따른 Stack Memory 공간에 대해서는 계산하기 어려워 생각하지 않는다.

즉, 공간을 차지하는 자료구조에 대해서만 계산한다.

ex) "입력이 N이

But, "문제"를 풀 때는 이러한 공간복잡도의 개념을 사용하진 않는다.

대신 "문제"를 풀때는 아래의 2가지 방법을 기반으로 배열의 범위등과 같은 자료구조 범위를 잡는다.

최대범위

문제에서 주어진 최대범위를 기준으로 메모리를 잡는다.

(1 <= N <= 1,000,000) => int[1000000]

메모리제한

문제에서 주어진 메모리 제한을 기준으로 계산해서 잡는다.

메모리 제한 : 512MB(512MB -> 512,000,000Byte) -> int a[128000000] // 512 % 4(int) => 128