출처
- 해당 post는 https://www.youtube.com/watch?v=NFETSCJON2M&t 영상을 보고 정리한것 입니다.
1. 시간 복잡도 (Time Complexity)
- 데이터 구조의 오퍼레이션 혹은 알고리즘이 얼마나 빠르고 느린지 측정하는 방법
- 빠르고 느린지는 1분 1초, 즉 시간을 측정하는 것이 아니라 얼마나 많은 단계(Steps)가 있는지로 측정함
- 같은 작업을 하는데 5단계를 요구하는 알고리즘A와 20단계를 요구하는 알고리즘B 중에 더 좋은 알고리즘은 당연히 5단계를 요구하는 알고리즘A이다.
- 즉, 알고리즘A가 알고리즘B 보다 시간복잡도가 더 훌륭한 알고리즘이다.
2. Memory 관점의 Array
- 휘발성 메모리 (Volatile Memory) : 컴퓨터를 껐다 키면 데이터가 보존되지 않고 사라짐, 즉 지속적인 전력 공급을 요구함. 대표적으로 Ram이 있다.
- 비 휘발성 메모리 (Non-Volatile Memory) : 컴퓨터를 껏다 켜도 데이터가 보존되는것, 즉 지속적인 전력 공급을 요구하지 않음. 대표적으로 HDD, SSD와 같은 하드디스크가 있다.
- 프로그램이 돌아가고 변수들이 저장되는것은 휘발성 메모리 즉, RAM에 저장이 된다. Random Access Memory 이기 때문에 더 빠르다.
3. RAM (Random Access Memory)
- Ram을 여러개의 박스들의 집합이라고 정의한다면 각 박스들에는 데이터를 보관할수 있다.
- Ram에서는 박스들을 Memory Address 라고 한다.
- 프로그램이 2번 Memory Address에 접근을 하려고 한다면 순차적으로 1번 이후에 2번에 접근하는것이 아닌 바로 2번에 접근이 가능하다.
- 이를 Random Access Meomory라고 하며, Random Access Memory는 내가 원하는 Address에 바로 접근하기 때문에 빠르다.
- 예를들어 5번 Random Adress를 접근하고 싶다면 1,2,3,4를 거치지 않고 바로 5번 index에 접근이 가능하다.
4. Array에서의 Ram
- Array를 만들때 컴퓨터에게 Array의 길이를 알려주어야 한다.
- 예를들어 A라는 Array는 4개의 길이를 가진다. 그렇다면 Ram에 4개의 연속된 박스를 할당 받아야한다.
- 컴퓨터는 Array를 Ram에서의 시작위치와 길이를 알고 있다.
- Python과 Javascript는 길이와 할당 요청을 자동으로 하고 있기 때문에 생소 할수 있다.
- 처음에는 Array의 길이를 신경쓰지 않고 프로그래밍을 하게 되다가, 데이터 구조, 알고리즘을 배우면서 알게 된다.
- 즉, Python과 Javascript는 Array의 할당을 자동으로 해주고 있기 때문에 신경쓰지 않으면 Array의 길이가 길어지게 되고 속도가 느려지게 된다.
5. Array의 Read
- Array는 0부터 indexing을 한다.
- 위치만 알면 배열의 데이터에 접속할수 있다.
1
['파스타','아이스크림','피자','토마토']
- 위 처럼 4개의 요소를 가지고 있는 Array가 있다고 했을때 피자를 가져오고 싶다면 컴퓨터에게 2번 index의 데이터를 요청하면 된다. (Array의 index는 0번부터 시작한다.)
- 따라서 Array에서 Read하는것은 엄청 빠르다. 왜냐하면 컴퓨터는 Ram에 Array의 index를 저장하고 있기 때문이다.
- 많은 데이터를 읽어야 한다면 Array가 속도가 빠르다.
- index에서 요소를 읽어내는 속도는 동일 하기 때문에 Array의 길이와는 상관없이 빠르다.
- 즉, Array의 요소가 5개이든, 100개이든 Read하는것은 하나의 단계이다.
6. Array의 Search
- Search은 내가 원하는 원소가 어디에 있는지, 그리고 실제로 있는지도 모르기 때문에 원소를 0번부터 하나씩 모두 찾아봐야 한다. 때문에 Read와는 달리 속도가 느리다.
1
['파스타','아이스크림','피자','토마토']
- 위처럼 4개의 요소를 가지고 있는 Array가 있을때, 피자가 있는지 확인하고 싶다면 0번의 파스타부터 Search을 하게 된다. (우리 눈에는 3번째에 피자가 있지만, 실제 프로그램은 0번 index부터 하나씩 순서대로 Search을 한다.)
- 이는 Random Accese 때문에 Memory의 박스에는 쉽게 접근이 가능하지만, 해당 박스에는 어떤 데이터가 있는지는 모르는 상황이다.
- 만일 피자가 Array의 0번째에 있다면 바로 찾을 수 있겠지만, 원소가 1000개의 Array의 제일 마지막에 있다면 Search하는데 시간은 엄청 오래 걸릴것이다.
- 이처럼 처음부터 순서대로 0부터 끝까지 차근차근 찾는걸 Linear Search 이라고 한다.
7. Array의 Insert or Add
1
['파스타','아이스크림','피자','감자','']
- Array를 만들때는 미리 길이를 만들어 놔야 한다. 즉, 위처럼 5개의 길이를 가진 Array라고 해야하는것 이다.
- 위처럼 5개의 원소를 가지는 Array가 있는데, 그중 4개에만 원소가 있고 나머지 하나는 없다는 상황에 토마토를 추가하고 싶다면 어떻게 해야할까?
1
['파스타','아이스크림','피자','감자','토마토']
- 가장 좋은것은 위처럼 맨 뒤에 토마토를 추가하는 것이다.
- 컴퓨터는 Array의 시작위치와 index를 알고 있기 떄문에, Array의 제일 끝으로 이동해서 토마토를 insert 해주면 된다.
- 하지만 Array의 중간이나, 맨 처음에 insert를 하고 싶을땐 어떻게 될까?
1
2
['토마토','파스타','아이스크림','피자','감자']
['파스타','아이스크림','토마토','피자','감자']
- 위와 같은 경우에는 Array의 index값이 달라지게 된다.
- 토마토가 맨 앞에 위치하게 된다면 나머지 원소들의 index는 각 +1씩 되야 하기 때문이다.
- 혹은 토마토가 중간에 위치하게 된다면 토마토보다 뒤에 있는 원소들의 index도 +1이 되야 한다.
- 가장 안좋은 경우는 Array의 길이가 4개로 빈 공간이 없는데, 원소를 추가해야 할때이다.
- 이때는 기존의 Array보다 더 큰 Array를 만들고 더 큰 Array에 기존의 Array 값을 복사한뒤 새로운 원소를 추가 한다.
- 그렇기 때문에 insert의 경우 삽입되는 위치 및 Array의 공간에 따라서 속도가 느려질 수 있다.
Array의 Delete
- Delete도 insert와 마찬가지로 위치에 따라 달라지게 된다.
1
2
['토마토','파스타','아이스크림','피자','감자','김치']
['토마토','파스타','아이스크림','피자','감자']
- 만일 위의 Array에서 제일 마지막 원소인 김치를 Delete하고 싶다면 컴퓨터는 Array의 시작 위치와 길이를 알고 있기 때문에 제일 마지막 원소로 이동하고 삭제하고 끝난다.
- 하지만 Array의 중간이나 제일 처음 원소를 삭제하고 싶다면 Insert때와 마찬가지로 삭제한 원소에서 생기는 빈 공간을 채워주어야 한다.
1
2
3
['파스타','아이스크림','피자','감자','토마토']
['파스타','아이스크림','','감자','토마토']
['파스타','아이스크림','감자','토마토']
- 위의 Array에서 피자를 삭제하고 싶다면 우선 중간의 피자를 삭제하고 생긴 공간을 이후 뒤의 감자, 토마토의 원소들로 채워주게 되고 index가 -1씩 되게 된다.
1
2
3
['파스타','아이스크림','피자','감자','토마토']
['','아이스크림','피자','감자','토마토']
['아이스크림','피자','감자','토마토']
- 이번엔 맨 앞의 파스타를 삭제하고 싶은 경우에도 파스타위치에 빈 공간이 생기게 되고 나머지 맨 뒤의 원소들이 빈 공간을 채워주되게 되며 index가 -1씩 된다.
- 길이가 긴 Array에서 원소들의 index가 변경될때는 많은 단계가 소요되게 되므로 속도가 느려지게 된다.
Array Summary
- Array는 데이터를 Read할때는 Random Access 때문에 속도가 굉장히 빠르다.
- 하지만 Search, Insert, Delete 할때는 위에서 이야기한바와 같이 단계가 많아지게 되므로, 느려지게 된다.
- Array에서 Insert, Delete를 해야할 때라면 Array의 맨 마지막에서 하는것이 가장 빠르고 좋을것이다.