자료구조의 기능들과 시간복잡도 분석

#자료구조 #자료구조기능 #자료구조시간복잡도

​

AI스쿨 msa기반 java 백엔드 코스 중에 공부한 내용을 작성하였습니다

자료구조(배열, 리스트, 큐, 스택)

이전글을 통해 자료구조 배열, 리스트, 큐, 스택에 대해 알아보았습니다. 이번글에서는 각 자료구조가 가지고 있는 순수 기능들과 그 기능들의 시간복잡도에 대해 알아보고자 합니다.

배열(Array)

배열의 기능

배열은 같은 종류의 데이터가 고정된 크기로 존재하는 자료구조입니다. 순수 배열에서는 알려진바와 달리 삽입, 삭제 기능이 없으며 값이 비워져있는 경우도 없습니다.(초기값으로 0이나 임의의 값을 설정함)

배열은 수정만 가능합니다. 특정 인덱스의 값을 가져와 수정만 하면됩니다. 그 외의 기능들은 구현이 가능하지만 순수한 배열의 기능은 아닙니다.

​

선언

배열을 생성할때의 시간복잡도는 O(n)입니다. 배열의 요소를 하나 하나 차례대로 생성해 감을 생각해보시면 됩니다.

​

접근

배열의 접근하는 시간복잡도는 O(1)입니다. 어떤 인덱스든 간에 접근 속도는 동일합니다.

​

수정

배열의 수정은 특정 인덱스의 값만 변경해주면 됩니다. 따라서 O(1)입니다.

리스트(list)

리스트의 인덱스

리스트는 사실 인덱스가 존재하지 않습니다. 파이썬의 리스트는 배열의 장점과 리스트의 장점을 섞어 놓은 배열도 리스트도 아닌 자료구조입니다. 프로그래밍 언어마다 자료구조에는 차이가 있어 순수한 배열과 리스트가 있는 언어도 있고, 파이썬 처럼 없는 언어도 존재합니다.

​

리스트의 기능

리스트는 자신과 양 옆으로만 알 수 있습니다. 다음과 같은 기능이 존재합니다. 간단하게 생각할 수 있어서 바로 시간복잡도를 표기해 두겠습니다.

​

1. 현재 값을 읽는다.O(1)

1. 현재 값을 수정한다.O(1)

1. 현재 값을 삭제한다.O(1)

1. 옆칸에 값을 추가한다.O(1)

1. 옆칸으로 이동한다.O(1)

1. 맨처음으로 이동한다.O(1) or O(n) - 구현에 따라 다르다

​

+ 4번 추가설명: 옆칸에 값을 추가할 경우 두가지 동작만 하면됩니다. 1. 새로운 값을 현재 값 다음에 놓기 2. 새로운값을 이전 다음값 전에 놓기

​

+ 6번 추가설명: 맨처음에 속하는 값을 따로 배놓으면 O(1)이 가능하지만, 처음을 향해 현재부터 하나 하나 이동시에는 O(n)입니다.

스택(Stack)

스택의 기능

스택의 기능은 맨 뒤에 값을 넣는다(PUSH), 맨 뒤에 값을 뺀다.(POP) 두가지가 있습니다. 추가로 포인터로 맨 위의 값을 지정할 수 있습니다.(TOP)

​

PUSH

맨 마지막 자리에 값을 넣기만 하면 되므로 O(1)

​

POP

맨 마지막 값을 삭제하기만 하면 되므로 O(1)

큐(queue)

큐의 기능

스택과 마찬가지로 queue의 기능은 두가지입니다. 맨 뒤에 값을 넣는하는 ENQUEUE 맨 앞의 값을 빼는 DEQUEUE. 각각 PUSH, POP으로 불리기도 합니다.

​

추가로 스택의 포인터를 지정할 수 있습니다. front(나가는쪽)-rear(들어가는 쪽) or head - tail입니다.

​

ENQUEUE

맨 마지막 자리에 값을 넣기만 하면 되므로 O(1)

​

DEQUEUE

맨 엎의 값을 삭제하기만 하면 되므모 O(1)

​

​

---

반복문 복습글을 좀 작성하고 나서부터는 자료구조를 파이썬으로 직접 구현하는 글을 남겨볼까 합니다 :D