[CS] 시간복잡도와 배열의 기초 개념을 알아보자

시간 복잡도란?

데이터 구조의 작동 혹은 알고리즘의 속도를 측정하는 것

얼마나 많은 단계가 있는가로 측정된다. (초/분의 개념이 아니라 단계가 적을 수록 좋다.)

 

배열 이야기 전에 메모리에 대해 알아보자.

메모리는 비휘발성 메모리와 휘발성 메모리 2가지 종류가 있다.

 

휘발성 메모리	비휘발성 메모리
컴퓨터를 끄면 휘발된다	컴퓨터를 꺼도 휘발되지 않는다
RAM	하드 드라이브

 

두 메모리 중 어떤 것의 데이터를 읽을 때 속도가 더 빠를까?

휘발성 메모리에서 데이터를 읽을 때 속도가 더 빠르다.

 

RAM, Random Access Memory는 데이터 접속을 랜덤으로 할 수 있다.

RAM을 어떤 상자들의 그룹이라고 할 때, 각 상자별로 이름이 정해져 있다.

이 이름을 Memory Address라고 한다. 그래서 어떤 데이터를 찾을 때 Memory Address 2번으로 가라 하면 바로 그 데이터에 접근할 수 있다. 1번, 2번 이런 식으로 순차적으로 접근하지 않고 바로 접근할 수 있기 때문에 속도가 더 빠른 것이다.

---

배열에 대해서

우리가 배열을 만들려면 배열의 길이가 얼마나 긴지 사전에 정해주어야 한다.

상자들이 나란히 위치할 수 있도록 만들어줘야 하기 때문인데... JS와 Python은 이렇게 정해줄 필요가 없다! 

 

간단하게 이유를 알아봤다.

자바에서 배열을 만들 때는 아래처럼 정해진 크기로 배열을 선언해야 한다.

int[] myArray = new int[5];

5개의 int 값을 저장할 수 있는 고정된 크기의 배열을 선언했다.

만약 고정된 크기를 초과해 값을 저장하거나, 배열의 크기를 줄이려면 새로운 배열을 생성해 데이터를 복사해야 한다. 이러한 조정 작업이 번거롭기 때문에 배열 크기를 동적으로 조정해야 하는 경우에는 ArrayList라는 동적 배열 구조를 활용하곤 한다.

 

반면 자바 스크립트에서 배열을 만들 때는 상당히 유동적이다.

let myArray = [1, 2, 3];

자바 스크립트에서는 배열의 크기를 동적으로 조절할 수 있어 필요에 따라 요소를 추가/제거할 수 있다.

 

두 언어에서 이렇게 차이가 생기는 것은 자바는 정적 타입 언어고, 자바 스크립트는 동적 타입 언어이기 때문이다. 각 타입 언어는 각각의 장점과 단점을 갖고 있다. 아무튼 자바 스크립트로 개발을 하는 나는 배열의 길이를 사전에 정하지 않아도 된다는 의미가 무엇인지 궁금해서 잠깐 알아봤다.

 

(아무튼) Reading

자바 스크립트로 개발을 한다면, 인덱스만 알면 데이터에 접근할 수 있다.

배열이 얼마나 긴지 상관 없이 인덱스만 알면 그 인덱스를 달라고 하면 되기 때문이다.

여기서 중요한 건 [Reading] 이라는 것. 2번 인덱스 읽어줘! 하면 2번 인덱스의 값을 가져오는 것이다.

 

Searching

피자를 갖고 싶은데 피자가 어디에 있는지 모른다.

그럼 모든 상자를 다 열어서 피자 여기 있냐? 하고 찾아 다녀야 한다.

이 때 운 좋게 0번 인덱스에 피자가 있다면 바로 찾지만, 맨 끝에 있을 때도 있고 아예 없을 때도 있다.

따라서 Reading보다 시간이 오래 걸린다. 이런 경우를 선형 검색(Linear Search)이라고 한다.

 

Insert (Add)

past, ice cream, pizza, potato만 있을 때 2번째 인덱스에 tomato를 넣고 싶다면?

ice cream 뒤에 있는 데이터들을 다 옮겨줘야 한다.

 

추가할 데이터를 맨 끝에 붙이면 좋겠지만, 이렇게 중간 혹은 맨 앞에 추가한다면 그 뒤의 데이터을 모두 하나하나 옮겨주어야 한다. 만약 배열이 크다면 이걸 다 하나씩 옮기는데에 시간이 많이 소요될 것이다. 

 

Delete

추가와 마찬가지로 배열의 마지막 요소를 삭제하고 싶다면 그냥 삭제하면 된다.

하지만 중간이나 앞을 삭제하면 공백을 없애기 위해 앞으로 이동을 해야 한다.

---