Array 배열이란?

#Array #코딩 #노마드 코더

본 포스팅은 노마드코더 영상을 정리하며 학습하기 위한 목적을 가지고 있습니다.

---

Array 배열이란?

시간복잡도(time complexity)는 데이터 구조의 오퍼레이션 혹은 알고리즘이 얼마나 빠르고 느린지 측정하는 방법.

실제 시간 측정이 아니라 얼마나 많은 단계가 있는가로 측정한다. 당연히 단계가 적을수록 좋다.

 

메모리는 non-volatile Memory vs volatile Memory 두가지 경우가 있다.

비휘발성 메모리는 하드디스크 같은 것이고 휘발성 메모리는 RAM과 같은 것이다.

데이터 접속을 랜덤으로 하니까 빠르다. 순차적이 아니라 5번째를  가고싶으면 5번째로 갈 수 있다.

배열을 만들때에는 얼마나 긴지 알려줘야 한다. 왜냐하면 컴퓨터는 그 길이를 알아야 그 공간을 미리 예약해야하기 때문이다. js, python은 자동으로 핸들링하기 때문에 직접 다뤄줘야 하는 C보다 느릴 수 있다.

길이가 5인 배열 주소 할당

 

Array의 동작 원리

1. Reading

  배열에서 읽어내는 건 빠르다. 어떤 인덱스든 속도는 동일하니까 많은 자료를 읽어야 하면 배열이 짱이다.

2. Searching

  시간이 쫌 걸린다. 선형 검색은 그닥 빠르지 않다. 이유는 우리는 배열안에 무엇이 들어있는지 알기 위해서는 하나씩 다 열어봐야 하기 때문이다.

3. insert

  맨 마지막에 넣는건 빠르다. 최악의 시나리오는 맨 앞에 넣는것 왜냐하면 첫번째 인덱스에 넣기 위해서는 기존의 것을 오른쪽으로 다 옮겨야 하기 때문이다. 두번째 최악의 시나리오로는 꽉 차 있는 경우 새로 만들어서 이전 배열 복사 후 하나 추가하는 것도 있다.

4. delete

 보통 시나리오는 배열 중간 요소 삭제이다. 공백을 채우기 위해서 나머지가 움직여야 한다. 그렇다면 최악은 당연히 맨 앞에 것을 지우는 것이다. 맨 첫번째를 옮기기 위해서는 공백을 채우기 위해 다 움직여야 하기 때문이다.

 

결론

Array는 읽기가 굉장히 빠르다. 하지만 수정하거나 검색하기에는 오랜 시간이 걸릴 수 있다.

---

오늘 성장에 도움을 주신 니꼴라스 쌤

출처: https://www.youtube.com/watch?v=NFETSCJON2M&t=294s&ab_channel=%EB%85%B8%EB%A7%88%EB%93%9C%EC%BD%94%EB%8D%94NomadCoders