인프런 커뮤니티 질문&답변

Array배열의 경우

시작주소+ 4*(n-1) 즉 아무리 긴 배열이더라도

한번의 연산으로

원하는 데이터에 접근할 수 있기 때문에

배열 요소에 접근할 때의 시간복잡도는

O(1)입니다. 여기까지는 이해가 갑니다.

그런데 동적 배열 8:16초에서

Dynamic Array의 선언 및 초기화의 시간복잡도가 왜 O(n)인지 이해가 가지 않았는데요

질문1.

예를 들어 배열의 사이즈가 3인 경우 (자바로 예를 들어 보겠습니다.)

int[ ] array = { 10, 20, 30 };

이런 경우 배열의 요소가 3개이므로

주소값에 3번을 접근해야 하고,

int[ ] array = {1, 2, 3, 4, 5};

배열의 요소가 5개 일때는

주소값에 5번을 접근해야 하며,

int[ ] array = { 1, 2, 3,... n};

배열의 요소가 n개 일때는

주소값에 n번을 접근해야 한다.

따라서 배열의 선언 및 초기화의 시간 복잡도는 O(n)이다.

제가 이해한 게 맞는지 답변 부탁드립니다.

<질문하는 의도>

"강사님께서 배열에 n개의 데이터를 저장해야 하기 때문에 배열의 선언 및 초기화의 시간 복잡도는 O(n)이다."라고 말씀하셨는데,

제가 중간이 이해가 가지 않아서요 

질문2.

추가적으로 덧붙이자면

메모리의 해당 번지에 있는 값을 삭제하기 위해서도 그 번지(주소)에 접근해야 하고,

메모리의 해당 번지에 값을 추가하거나 할당하기 위해서 그 번지(주소)에 접근해야 되잖아요.

그러면 메모리주소에 "접근"이란 말은 삭제, 할당, 수정, 삽입, 모든 경우에 다 통용되는 단어인거죠??