[3주차] 시간복잡도, 공간복잡도 계산

시간복잡도 

언제?) 항상 문제 풀기 전에 계산하고 시작

1억번당 1초 -> 만만억 (만 곱하기 만은 억)

for문은 O(N), 이중 for문의 경우 O(N^2)

스택은 O(1)인데, 연산횟수가 N번이라면 O(N)

 

 

공간복잡도

언제?) 1) 재귀함수 쓸 때 2) n이 일의 자리숫자까지..? 뭔가 느낌 이상할 때, 3) 제한 조건들이 빡빡할 때

int형은 4바이트(32bit 기준)

1KB = 2**10B = 1024B

1MB = 2**10KB = 1024KB

 

배열 한 칸당 int형 들어가면, 

메모리 제한이 256MB 라면,

256MB = 2**8MB = (2**8) * (2**10)KB = (2**8) * (2**10) * (2**10) B = 2**28 B

int형 배열은 (2**28) / 4 만큼 생성 가능