용기러기's Coding World

자료 구조에 따른 시간 복잡도 비교 - 배열편 본문

용기러기's 알고리즘

자료 구조에 따른 시간 복잡도 비교 - 배열편

yongkis 2020. 9. 8. 14:25

오늘은 '알고리즘', 즉, 문제를 해결하는 방법 혹은 절차가

얼마나 효율적인지 (상대적인 개념)를  체크하는 기준이 되는

'시간 복잡도' 그리고 '공간 복잡도' 중에서 '시간 복잡도'를 위주로

 

특정 '자료구조(자료를 저장하거나 사용하는 방법을 정의해 놓은 것)'를

사용했을 때, 자료의 '추가', '삭제', '조회', '탐색'에 있어서

시간 복잡도가 얼마나 되는지를 통해 

어떤 상황에는 어떤 자료구조를 쓰는 것이 좋은 것인지를

고민해보는 시간을 가져보고자 한다 :D 

 

그럼 가장 먼저 볼 자료구조는!

배열(Array)! :D 입니다.

 

먼저, 우리가 흔히 아는 Array(C언어와  Java의 배열과 같이 길이가 정해져있는 배열을 말함)!

참고로, 자바스크립트, 파이썬 등의 언어에서의 배열은

길이 제한이 없는 배열이기에 여기에서의 해석에는 맞지 않을 수 있습니다 :D 

 

그럼 다시 배열로 돌아와서!

배열 또한 자료구조 중에 하나인데,

특징을 간단하게 정리해보면, 배열은 

 

- 생성시에 길이(메모리 할당)가 정해지며 생성되고, 따라서, 그 메모리 이상을 쓸 수 없고, 그 메모리 이하를 쓰게되면

나머지는 일종의 메모리 낭비가 되는 것이다.

- 번호가 있는 자료구조이다. 즉, 0번째에는 어떤 자료, 1번째에는 어떤 자료 ... 이런식으로

자료에 index를 부여해서 저장 및 사용하는 자료구조이다.

 

이렇게 간단하게 배열을 살펴봤으니!

배열의 시간 복잡도를 살펴보면,

자료 출처 : 코드스테이츠

먼저,

 

1) 조회(Lookup) => O(1) 

why? : 자료마다 인덱스를 부여해뒀기 때문에,

조회가 굉장히 편리하다. 예를 들어, 개인마다 창고가 있을 때, 귀찮지만

보관할 때마다 번호를 붙여서 자기만의 표시를 해두고 관리하는 사람은

다음에 그 물건을 꺼내고자 할 때 헤매지 않고, 그 물건이 1번 섹션에 있었지 하고 찾으면 된다.

 

2) 삽입(insert) => O(n)

why? : 전에 말했듯이 배열은 본래 길이가 정해져있는 자료구조이다. 

가로로 된 알약통 

 

을 배열이라고 가정했을 때,

특정 위치에 자료를 추가하고자 할 때,

즉, 위에 알약통은 현재 7개의 섹션으로 나눠져있는데,

그것을 8개로 추가하고 싶다면,

맨뒤의 'S' 섹션 뒤에 또다른 섹션을 추가하고, 

만약 'W' 섹션 바로 뒤에 (W와 T사이) 자료를 추가하고자 한다면

W섹션 뒤에 새로 자료를 추가하고, T,F,S는 차례대로 뒤로 한칸씩 밀게 된다.

이 때, '차례대로 뒤로 한칸씩 밀게되는' 이 과정에서

O(n)의 시간복잡도가 생긴다. 

 

이 때, 제거도 마찬가지로 O(n)이 되는데,

이유는 위와 유사하다.

제거 또한, 중간에 특정 섹션을 삭제하고,

그 뒤의 섹션들을 차례대로 삭제한 세션의 공석을 채우면서 한칸씩 앞으로 밀게 되므로

이 작업이 n번 실행되기 때문에 O(n)이 된다.

 

다음으로, 할당(assign)은 O(1)인데, 그 이유는

배열은 인덱스로 관리되기 때문에 

3번째 인덱스에 있는 자료를 수정하고자 할 때

배열[인덱스] = 바꿔주고자하는 값; 을 해주면

바로 변경이 가능하다

 

마지막으로, 탐색(find)는 배열이 인덱스로 되어있더라도

특정 값을 찾기 위해서는(인덱스가 아닌)

결국 배열 속의 모든 요소들을 살펴봐야하기 때문에

O(n)의 시간 복잡도를 갖게 된다. 

 

그렇다면 배열은 어떤 상황에서 쓰기 좋을까?

간단한 예시로 책장을 생각해볼 수 있을 것 같다:D 

 

집에도 하나씩은 있는 책장의 한층을

하나의 배열이라고 하면

그 안의 책은 자료가 된다.

그리고 맨 앞부터 차례대로 0부터 n의 인덱스를 부여한다고 했을 때,

새로 산책을 중간에 넣으려면, 본래 있던 책들은 한칸씩 뒤로 밀리게 된다(새 책을 넣으려는 위치의 뒤부분만).

또한, 책장에서 책을 하나 꺼내려고 한다면(제거), 꺼내는 책의 위치를 기준으로 뒤의 책들은 한칸씩 앞으로 땡겨지게 된다.

그리고, 책장에서 원하는 책을 찾고자한다면? 

인덱스에 해당하는 책의 이름을 모두 외우고 있다면, O(1)이겠지만(이게 가능한 자료구조가 해시테이블이지만 후에 포스팅할 예정)

결국, 앞에서부터 책 제목을 하나하나 보는수밖에 없기에 O(n)이되고,

만약, 놀러온 친구가

저 책장에서 3번째 책좀 꺼내줘봐 라고 했다면? 바로 3번째 책을 꺼낼 수 있기 때문에 O(1)이 된다.

 

좀 더 심화해보면, 책장의 한층은 1차원 배열이되고,

그 책장이 2층, 3층이 된다면 이것이 2차원 배열이 될 것이다. 

 

생각하기는 싫지만, 3차원 배열이 된다면

이런 구조가 될 것이다. 

 

굳이 배열로 표현해보면 아래와 같고,

3차원 배열 속에 책들이 들어있을 것!:D 

2차원 배열은 책장의 한 층이 되고,

1차원 배열은 책장 전체가 된다.

 

1차원 배열 [

   2차원 배열 [  3차원 배열 [      ],   3차원 배열 [      ] ,   3차원 배열 [      ]      ]

   2차원 배열 [  3차원 배열 [      ],   3차원 배열 [      ] ,   3차원 배열 [      ]      ]

   2차원 배열 [  3차원 배열 [      ],   3차원 배열 [      ] ,   3차원 배열 [      ]      ]

   2차원 배열 [  3차원 배열 [      ],   3차원 배열 [      ] ,   3차원 배열 [      ]      ]

]

 

그럼 여기까지

배열이라는 자료구조를 시간 복잡도와 연관해서 살펴봤고,

배열에서의 추가, 삭제, 조회, 탐색 등이 시간 복잡도가 얼마나 되는지

그리고 실제 배열이 어떤 사례에 비유될 수 있는지를 살펴봤습니다 :D