자료구조와 복잡도

자료구조

• 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합을 의미한다.

시간복잡도

• "문제를 해결하는 데 걸리는 시간과 입력의 함수 관계" 를 가르킨다.
• 로직이 얼마나 오랜 시간이 걸리는지를 나타내는 데 사용한다.
• 보통 빅오 표기법으로 나타낸다.

빅오 표기법

• O(n) 기호로 표기
• 입력 범위 n을 기준으로 로직이 몇 번 반복되는지 나타낸다.

시간 복잡도의 존재 이유

• 효율적인 코드로 개선하는 데 쓰이는 척도가 된다.
• O(n^2) = 9초를 개선하여 O(n) = 3초가 걸리게 할 수 있다.

시간 복잡도 비교

• O(n^2) > O(n) > O(logN) > O(1)

공간복잡도

• 프로그래밍을 실행시켰을 때 필요로 하는 자원 공간의 양을 의미한다.
• 정적 변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함된다.

int a[1004]; // a배열은 1004 * 4byte의 크기를 가지게 된다.

자료 구조에서의 시간 복잡도

평균 시간 복잡도

최악의 시간 복잡도

---

참고 자료

면접을 위한 cs 전공지식 노트