[PS] 시간 복잡도 & 공간 복잡도

빅오 표기법

빅오 표기법은 시간 복잡도를 표현할 때 사용되는 표현으로 O(1) , O(N) 등과 같이 사용된다.

// O(1)
for(int x=0; x<10; x++){ }

// O(N)
for(int x=0; x<n; x++){ }

//O(N^2)
for(int x=0; x<n; x++{
	for(int y=0; y<n; y++{
    }
 }

O(logN)이라는 빅오 표기법도 있지만 log(1억) = 27이 되기 때문에, O(1)로 생각해도 된다.

N값을 통한 힌트 얻기

P.S 문제는 몇 초내에 풀 것이라는 조건이 있기도 하다. 1초 -> 1억번의 반복횟수를 얻을 수 있다. 보통 3초를 준다.

N = 1000이고 3초까지 허용한다면, 몇중 for문 까지 돌릴 수 있을까요?
3초 * 1억 = 3억, N^2 = 1,000,000 / N^3 = 1,000,000,000
3중 for문은 10억번 반복횟수이고 2중 for문은 100백만 반복횟수이므로 2중 for문 까지 돌릴 수 있다.

이를 통해 N의 값에 따라 어떤 문제 유형인지 파악가능하다.

보통)
BFS : N(100~200)
완점탐색 : N(~30)
2차원 DP N([1000][1000])
DP, 그리디 N(100,000)

공간 복잡도

자주 사용하는 자료형인 int와 char만 생각해보겠습니다.
int 크기 : 4Byte
char 크기 : 1Byte

int v[1000][10000] : 4 x 1000 x 10000 = 40MB
1K = 1,000
1M = 1,000,000

지역/전역 변수 범위

stack : 지역변수가 저장되는 메모리 공간의 이름 (공간 : 128KB ~ 2MB)

128KB Stack 공간일 때 최대 int형 변수 배열 개수는?
128,000 / 4(Byte) = 32,000
Ans) int arr[32000]

결론으로는 범위를 10만개 넘는다고 생각하면, 전역으로 올리는게 좋다!