[자료구조] 배열(Array)

*** 개인이 공부한 내용들을 간략하게 정리하고 참고하기 위한 포스팅입니다. 설명에 실수가 있을 수 있습니다. 지적해 주시면 정말 감사하겠습니다. ***

 

정의 : 연속된 정수로 인덱싱된 같은 type의 원소들의 집합. 

 

1. Add 

1-1) sorted array : 순서를 유지하기 위해 shifting을 통해 공간을 만들어야 하므로, time complexity는 O(n)이다.

1-2) unsorted array: array의 끝에 원소를 더하면 되므로 time Complexity는 O(1)이다.

 

2. Remove

1-1) sorted array: shifting을 통해 삭제된 공간을 메워 줘야 하므로, time Complexity는 O(n)이다.

1-2) (삭제할 index가 주어졌다는 가정 하에) 삭제할 index의 원소와 마지막 원소를 바꾸고 마지막 원소만 지우면 되므로, time Complexity는 O(1)이다. 

 

3. Find(Search)

3-1) linear search: iteration을 통해 찾고자 하는 원소를 찾는 방식. time Complexity는 O(n)이다.

3-2) binary search: sorted array에서만 사용 가능하며, time complexity는 O(logn). 자세한 내용은 후술한다.

 

Binary Search

binary search(이분 탐색)이란, sorted array를 반으로 나누고, 그 중 찾고자 하는 값을 포함하는 범위를 다시 반으로 나누는 것을 답을 찾을 때까지 반복하는 것이다. 개인 공부용 블로그 포스팅이기에 할 수 있는 표현이지만 그냥 술자리에서 하는 업&다운 게임이다.

 

Pseudo-Code는 아래와 같다.

left = 0
right = n-1
while(left<right):
	mid = (left+right)/2
    if(array[mid]<x):
    	left = mid+1
    else:
    	right = mid
if(left==right) and (array[left] ==x):
	found = True
    foundIdx = left
else:
	found=False

input 크기가 N일 때, 한 번 탐색을 수행할 때마다 N이 (1/2)N으로 줄어드므로, 최악의 상황에서는 (1/2)^k*N = 1이 된다. 따라서

(1/2)^k*N = 1

=> N = 2^k

=> log_2(N) = k

 

k는 탐색 횟수고 그것이 input에 log2를 취한 것에 비례하므로, Binary Search의 time complexity는 O(log_2(N)) = O(logN)이다.