Arrays

 

Arrays

- 배열은 선언시 크기만큼 공간을 메모리에 미리 예약/할당

 

메모리 관점에서 배열

1. volatile(휘발성)

- RAM(Random Access Memory)
- 컴퓨터를 끄면 삭제

- 속도가 빠름

- 요청하는 주소의 데이터에게 바로 접근 가능

 

2. non-volatile(비휘발성)

- 하드 드라이브

- 컴퓨터를 껐다 켜도 그대로 존재

 

 

Time Complexity(시간복잡도)

- 데이터 구조의 오퍼레이션 혹은 알고리즘이 얼마나 빠르고 느린지 측정

- 기준: 단계(steps)

 

1) Read: 인덱스 값으로 데이터를 얻음

  -> 많은 데이터를 읽을 때 가장 빠름

2) Search: 검색 값의 존재 여부 확인을 위해 모든 데이터와 순차적으로 비교 필요

  -> 데이터 양, 데이터의 위치에 따라 검색 수행 시간이 다름

3) Add/Insert

  - 배열의 끝에 추가할 경우: 빠름

  - 중간에 추가: 보통 -> 추가한 위치 뒤의 데이터를 이동

  - 맨 앞: 느림 -> 모든 데이터를 이동

  - 이미 꽉 찬 배열에 추가: 최악 -> 더 큰 배열에 카피 후 추가

4. Delete

  - 마지막 요소 삭제: 빠름

  - 중간/처음: 보통/최악

 

* Linear Search(선형 검색): 순서대로 0부터 차례로 검색

 

 

배열 정리

- 읽는 속도 빠름

- 검색/추가/삭제 속도 느림

- 추가/삭제는 맨 끝일 때만 효율적