[자료구조]ch2 - lesson 1. 배열의 연산, 배열의 이해

배열

 

배열은 주로 값을 담고 값을 배열에서 삭제하고 원하는 값을 배열에서 찾는다. 

삽입, 삭제, 탐색 연산

<삽입연산의 시간복잡도>

시간 복잡도는 최악의 상황에서의 시간복잡도를 이야기한다. 
배열이 주어졌을때, 앞이나 가운데에 값을 넣는다
-> 새로운 값이 들어갈 자리를 확보하기 위해 다른 값들이 한칸씩 이동해야 한다. 
삽입의 시간 복잡도는 O(N)이다. 

삽입하려는 장소

3

1

2

N번의 이동이 필요 

배열이 주어졌을때, 뒤에 삽입한다. 
-> 다른 값들의 이동이 전혀 존재하지 않으므로 O(1)의 시간복잡도를 가진다. 

3

1

2

삽입하려는 장소

<탐색연산의 시간복잡도>

가장 간단한 방법은 처음부터 모든 값을 훑는 것이다. 
맨 끝에 값이 존재한다면 모든 값을 탐색해야 하므로 -> 시간 복잡도는 O(N)이다. 

<K번째 원소 값 구하기>


배열은 index 기반으로 이루어졌기 때문에 k-1 번째 index를 참조하면 바로 k번째 원소를 구할 수있다. 
-> 시간 복잡도는 O(1)이 된다.