5.1 복잡도

5.1.1 시간 복잡도

• 시간 복잡도란 입력 크기에 대해 어떠한 알고리즘이 실행되는 데 걸리는 시간
• 주요 로직의 반복 횟수를 중점으로 측정되며, 보통 빅오 표기법으로 나타낸다.

<aside>

빅오표기법

입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것

</aside>

• 효율적인 코드로 개선하는 데 쓰이는 척도

  ex> O(n2) ⇒ O(n)

5.1.2 공간 복잡도

• 공간 복잡도는 프로그램 실행시켰을 때 필요로 하는 자원 공간의 양

5.2 선형 자료 구조

요소가 일렬로 나열되어 있는 자료 구조

5.2.1 연결 리스트

• 데이터를 감싼 노드를 포인터로 연결해서 공간적 효율성 극대화시킨 자료구조
• 삽입과 삭제가 O(1)이 걸리며 탐색에는 O(n) 걸림

1. 싱글 연결 리스트 : next 포인터만 가진다
2. 이중 연결 리스트 : next 포인터와 prev 포인터를 가진다
3. 원형 이중 연결 리스트 : 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드 가리킴

5.2.2 배열

• 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터 집합