배열의 정의와 성질

배열 - 메모리 상에 원소를 연속하게 배치한 자료구조.

 

배열의 성질

1 . O(1)에 k번째 원소를 확인/변경 가능. 

2. 추가적으로 소모되는 메모리의 양(overhead)가 거의 없음

3. Cache hit rate가 높음 

4. 메모리 상에 연속하 구간을 잡아햐 해서 할당에 제약이 걸림

 

 

임의의 위치에 원소를 추가 ,O(N) - 중간에 뭔가를 넣으려면 그 위치 이외에 것들도 다 밀어야 하니 O(N)

 

임의의 위치에 있는 원소를 제거 , O(N) - 이거도 중간에 뭘 지우면 그 위치 이외에 것들도 다 땡겨야 하니 O(N)