중간에 삽입하는 동안 동적 배열의 끝에서 삽입하는 이유는 O (n)입니까?

Question

따라서 Wikipedia 기사에 따라 동적 배열, 배열 끝에 삽입/삭제는 O (1)입니다. 중간에서 삽입/삭제는 O (N)입니다. 왜 그게 정확히?

또한 - 5 개의 요소가있는 동적 배열이 있고 위치 6에 새 요소를 삽입하면 작동은 O (n)이지만 기능을 사용하여 배열 끝에 추가되는 경우 O (1)입니다. 배열이 어느 경우에도 크기를 조정할 필요가 없다고 가정 할 때 동일한 작업이 아닌가? 아니면 동적 배열에 대한 추가가 실제로 6 위치 외에 새로운 요소를 삽입합니까?

감사!

편집하다: 내 주요 혼란은 배열 끝에 삽입하는 것과 배열 끝과 동등한 특정 위치에 삽입하는 것의 차이라고 생각합니다.

배열 끝의 메모리 주소에 대한 포인터가 유용하다고 생각합니다. 그래서 Append 작업이 빠릅니다. 반대로, 정확한 위치를 지정하면 (배열의 끝이더라도) 해당 위치에 삽입하는 것이 위에서 언급 한 메모리 주소를 사용하여 전체 배열을 통과해야한다는 것을 알 수 없습니다.

Answer 1

크기의 순서는 "동적 배열"이 실제로 어떤 종류의 데이터 구조에 의존 할 것입니다 ( "Dynamic Array"는 엄격하게 정의 된 데이터 구조가 아니며 특정 데이터 구조를 사용하여 달성되는 원하는 결과입니다). 당신이 제공하는 예는 링크 된 목록을 사용하여 달성 된 동적 배열로 반영되는 것입니다. 목록 구조가 최종 요소에 대한 포인터를 유지하면 끝에 추가하면 O (1)가 될 수 있습니다. (인덱스에 관계없이) 삽입하려면 링크 된 목록을 통과해야합니다. 즉, 원하는 인덱스까지 노드 당 하나의 작업이 의미합니다.

Answer 2

배열 끝에 삽입하려면 항목을 거기에 넣어야합니다.

배열의 중간에 삽입하려면 해당 지점 이후 항목을 하나씩 움직여야합니다.

배열 끝에서 삭제하려면 카운트를 하나 씩 떨어 뜨립니다.

중간에서 삭제하려면 그렇게해야합니다. 그리고 다른 항목을 아래로 이동하십시오.

그건 이동 그것은 그것을 o (n)으로 바꿉니다.

Answer 3

매우 간단합니다.

중간에 삽입하려면 각 후기 요소를 1로 이동하는 것이 포함됩니다. 마지막에 삽입하려면 추가 공간이 예약되어 있으면 품목이 저장되지만 새 공간이 할당되지 않으면 배정됩니다. 따라서이 작업은 수행됩니다 상각 일정한 시간.

Answer 4

Adam Robinson의 훌륭한 요약에 추가 : 이것은 단순한 이론이 아닙니다. 배열 끝에 반복적으로 추가하여 동적 배열이 구성된 여러 상황을 보았습니다. 이것은 O로 작동합니다(N**2) 성능은 배열을 반복적으로 재 할당해야하므로 각 멤버의 각 멤버를 새 배열 구조로 복사해야합니다. 재 할당은 Append Operations의 1/10에서만 발생할 수 있지만 충분히 나쁘고 여전히 O입니다.(N**2) 성능 측면.

STL에서는이 성과 페널티가 전화를 통해 피할 수 있습니다. vector::reserve(N) 벡터에 쓰기 전에; 그러나 그 단계는 종종 간과됩니다.

Answer 5

사실, 그것은 큰 것이 아니라 빅 테타.