자료구조 사전지식

1. 시간복잡도

- 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계

 

=> 쉽게 이야기하면 내 코드가 연산되는 횟수

 

1-1. Big - O 표기법

- 모든 경우를 고려했을 때 최악을 기준으로 시간복잡도 표현

- 가장 큰 영향을 주는 요소를 기준으로 표현

=> 상수항 무시

=> 계수 무시

=> 최고차망만 표시

 

But, 항상 시간복잡도가 크다고 해서 연산횟수가 많은 것은 아님

=> 데이터의 크기에 따라 결정

 

1-2. 그 외 표기법

- Big-Ω (빅 오메가): 최선의 시간 복잡도

- Big-θ (빅 세타): 평균적인 시간 복잡도

 

 

2. 공간복잡도

- 입력의 크기와 문제를 해결하는 데 필요한 공간의 상관관계

 

2-1. Bit & Byte

Bit

- 0,1 을 표현하는 데이터 양의 최소 기본 단위

Byte

- 1byte = 8bit

 

 

3. 배열과 리스트

 

혼동 요인..?

파이썬의 List, Java의 array, arraylist, Swift의 array.....

 

3-1. Java의 array, arraylist

array

- 고정 크기의 배열

- 선언 시, 크기 지정 -> 크기 변경 X

arraylist

- 동적 배열

- 밑의 파이썬의 List와 유사하게 동작

 

3-2. 파이썬의 List

- 동적 배열로 구현

- 요소를 추가할 때 메모리가 초과되면 내부적으로 더 큰 메모리 할당

- Linkedlist처럼 포인터를 통해 요소 연결 XXXXX

- 고정 크기의 배열을 사용하려면 array 모듈 Or Numpy와 같은 라이브러리 사용

 

3-3. Swift의 array

- 동적 배열로 구현

- 메모리가 연속적으로 할당

- 결국 파이썬의 리스트, 자바의 arraylist와 유사

 

3-4. 그래서 배열과 리스트의 차이는?

크기 조정 방법

- 동적 배열 VS 정적 배열

 

메모리 할당 방식

- 연속적 메모리 할당(Index 기반) VS 불연속적 메모리 할당(노드 기반)

 

요소의 삽입 삭제

- 삽입삭제시 O(n) VS O(1)

 

데이터 접근 속도

- O(1) VS O(n)

 

메모리 효율?

- 요소 자체만 저장 VS 데이터 + 포인터 저장

- 배열 크기를 초과할 땐? => 초과한 이후에 다시 요소들이 삭제된다면? => 그럼 배열 내에 남는 공간이 발생하겠네?