*시공간 복잡도

시간 복잡도

시간 복잡도는 입력에 따른 모듈의 문제 해결 소요 시간을 유추할때 활용합니다.

주로 빅오 표기법을 활용하며, 효율적인 코드 개선을 위한 기준으로 활용됩니다.

빅오 표기법

입력이 커졌을때 가장 영향을 많이 끼치는 항만 남기고 나머지(상수 등)을 제거한 표기법 입니다.

for(10)
	for(n)
		for(n)

for(n)

이러한 코드라면 입력(n)에 따라 10*n^2 + n의 시간 복잡도를 가지게 됩니다. 만약 이를 빅오 표기법으로 변경한다면, n^2 이 됩니다.

공간 복잡도

공간 복잡도는 프로그램을 실행하는데 필요한 자원의 양 입니다.

int[] arr = new int[10];

해당 코드는 10 * 4byte 의 공간을 필요로 합니다.

자료구조와 시간 복잡도

자료구조를 활용할때는 시간 복잡도를 신경써서 활용해야 합니다.

주로 해당 자료구조의 평균 시간 복잡도와 최악 시간 복잡도를 참고합니다.