[전지적 비전공자 시점의 CS] 1. 시간 복잡도와 Array

1. 시간 복잡도

• 데이터 구조의 오퍼레이션 혹은 알고리즘이 얼마나 빠르고 느리린지 측정하는 방법이다.
• 여기서 빠르기, 속도를 측정하는 단위는 시간적인 개념(분,초)가 아닌 얼마나 많은 '절차(=단계=steps)가 있는가로 평가된다.
• 예를 들어, 코드가 실행되고 return 값에 도달하기 까지 5개의 단계를 거쳐야하는 로직이 20개의 단계를 거쳐야하는 로직보다 빠르다고 평가할 수 있다.

2. Array

메모리 관점에서 배열을 지켜보자~!

1. 메모리 종류

1. 비 휘발성(non-volatile)

   • 컴퓨터를 재시동해도 데이터가 그대로 남아있는 특성 ex. 하드드라이브

2. 휘발성(volatile)

   • 컴퓨터 전원을 끄는 순간 데이터가 사라지는 특성 ex. Ram-memory
   • Ram?
     • Random Access Memory, 말그대로 원하는 곳 어디든 즉시 접근이 가능
     • 프로그램이 돌아가고 변수를 생성할 때 모두 Ram에 저장된다.
     • Ram은 이름 그대로 랜덤으로 메모리 주소에 접근할 수 있다.
     • 데이터를 순차적으로 다 찾는 것이 아니라 바로 원하는 메모리 주소로 접근이 가능하다.
     • Ex) 컴퓨터 사양에서 Ram 성능에 따라서 연산 속도에 영향을 많이 미친다. 게임을 실행하고 동시에 많은 액션이 동시에 실행되려면 어떤 위치에 어떤 데이터가 설정되어있는지 빠르게 검색이 가능해야한다.

3. 배열을 만들 때 Array의 길이를 컴퓨터에게 알려줘야 한다.

   • 배열을 만들 때 컴퓨터에게 미리 Array의 길이를 알려주면, 메모리 안에서 박스들이 나란히 위치할 수 있도록 공간을 계산하고 예약한다.
   • 이는 JS,Python에서 대신 작업을 해준다. 편한 기능이지만 속도의 저하를 불러올 수 있음
   • C언어 처럼 배열의 길이를 직접 설정해주면 즉각적으로 메모리가 반응한다. 컴퓨터가 연산을 통해서 예상할 필요가 없다.

2. Array의 Operation(Reading / Search / Insert(Add) / Delete)

1. Reading

   • 배열에서 원하는 요소값을 얻기 위해서는 index로 요청하면 된다.
   • 이미 컴퓨터는 Ram을 통해서 배열이 어디에 저장되어있고 길이가 얼마인지 기억하고있다.
   • 따라서 배열을 통해서 데이터를 읽어오는 작업은 시간 복잡도 평가가 좋다.
   • 요소가 100개든 100000개든 'index에 접근'이라는 스텝이 한 개이다.
   • 많은 데이터를 읽어오는 기능이 필요하다면 배열을 사용하는 것이 좋다.
   • 선형 검색(Linear Search): 순서대로 0부터 끝까지 값을 찾는 방법 => 속도가 느리다.

2. Search

   • '읽기' 보다는 속도가 저하된다.
   • 해당 요소를 검색하기 위해서는 원하는 요소가 나올때까지 스텝이 추가된다.
   • 인덱스를 통해서 데이터에 접근해서 읽어오는 것은 쉽지만 원하는 요소의 유무를 찾기 위해 검색하는 operation은 많은 스텝을 발생시킨다.

3. Insert

   • 배열에 요소를 추가하기 위해서는 방식과 메모리의 미리 할당된 배열의 길이의 상황에 따라 달라진다.
   • 만약 배열에 빈 공간이 남아있는 상태에서 맨 마지막 index에 데이터를 추가하는 것은 빠르게 완료할 수 있다.
   • 하지만 빈 공간이 남아있는 상태에서 마지막 index가 아닌 index에 요소를 추가하려면 뒤에 요소들이 한 칸씩 뒤로 밀려야한다. 한 칸씩 데이터가 밀려나가는 작업이 많아지면 많아질수록 시간 복잡도가 올라간다.

4. Delete

   • 배열에 요소를 수정하는 오퍼레이션은 맨 마지막 index의 데이터를 수정하는 것이 제일 좋은 성능을 가져온다.
   • 맨 마지막 index가 아니라면 밀려난 index만큼 데이터들이 이동해야하기 때문이다.

5. 결론

   • 배열을 핸들링 하려면 최대한 Index의 마지막 데이터를 수정하는 것이 최고의 시나리오이다.
   • 배열은 Reading 하는 기능은은 상당히 빠르지만, 데이터를 수정하는 기능(검색, 추가, 삭제)은 비교적 느리다.
   • 이러한 단점을 위해 Object와 성능을 올려주는 알고리즘들이 있다.

Reference

Youtube : Nomad Coder
Book : 자바스크립트로 하는 자료 구조와 알고리즘