복잡도

복잡도

• 알고리즘의 성능을 나타내는 척도

• 시간 복잡도

  얼마나 오래 걸리는지 → 필요한 연산의 횟수

• 공간 복잡도

  얼마나 많은 메모리를 차지하는지 → 필요한 메모리 크기

  메모리를 더 소모하여 시간을 줄일 수 있음 (Memoization)

Big-O 표기법

• 가장 빠르게 증가하는 항만을 고려하는 표기법

  ex) N개의 데이터를 모두 더한 값을 출력하는 프로그램 → O(N)

array = [1,2,3,4,5]
for i in array:
	for j in array:
			temp = i*j
			print(temp)

→ O(N제곱)

만약 코드 내부적으로 다른 함수를 호출한다면 그 함수의 시간 복잡도까지 고려해야 하므로

정확히 코드를 분석한 뒤에 시간 복잡도를 계산해야함.