5.1 복잡도

스터디를 함께 진행했음

자료구조란

효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합

복잡도

프로그램이 실행될 때 얼마나 많은 ‘시간’과 ‘메모리 공간’을 잡아먹는가를 의미하는 척도. 알고리즘의 효율성을 측정하는 척도이다.

시간 복잡도

문제를 해결하는 데 걸리는 시간과 입력의 함수 관계. 이 코드가 끝날 때 까지 시간이 얼마나 걸릴까?

빅오 표기법 : 입력 범위 n으로 해서 로직이 몇 번 반복되는지 나타내는 것.

공간 복잡도

프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양. 이 코드가 실행되는동안 메모리를 얼마나 차지할까?

정적 변수 뿐 아니라 동적으로 재귀적인 함수로 인해서 공간을 계속해서 필요로 하는 경우도 포함이다.