때로는 동적 메모리 할당을 사용하여 배열을 생성합니다. 동적 메모리 할당 기술을 사용하여 배열을 할당하는 경우 몇 가지 작업을 수행하여 배열 크기를 두 배로 늘릴 수 있습니다.
초기 배열 크기가 5라고 가정합니다.
배열
| 0 | 1 | 2 | 3 | 4 |
| 요소 1 | 요소 2 | 요소 3 | 요소 4 | 요소 5 |
배열을 두 배로 늘리면 크기는 -
입니다.| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 요소 1 | 요소 2 | 요소 3 | 요소 4 | 요소 5 | 요소 6 | 요소 7 | 요소 8 | 요소 9 | 요소 10 |
크기가 n인 배열 arr의 크기를 두 배로 늘리려면 arr[0…n-1]입니다. 처음에는 m이라고 하는 크기의 새 배열을 하나 만들어야 합니다. 그런 다음 n개의 요소를 arr에서 새 배열로 복사합니다. 마지막으로 새 배열을 가리키도록 arr 값을 변경합니다.
크기가 m인 배열을 생성하려면 θ(m) 시간이 걸립니다. 일부 기본값으로 초기화되기 때문입니다. 그런 다음 이전 어레이에서 새 어레이로 복사하는 데 추가 θ(n) 시간이 필요합니다. 따라서 작업에는 θ(m + n) 시간이 걸립니다. 이 작업은 어레이가 가득 찼을 때 발생합니다. 그리고 일반적으로 m 값은 2n과 같습니다. 따라서 복잡성은 θ(2n + n) =θ(3n)이 θ(n)과 동일합니다. 그러나이 작업은 비용이 많이 드는 것으로 간주됩니다. 그러나 이 작업은 하위 시퀀스 n 반복에 걸쳐 상각된 다음 반복당 θ(1) 시간만 추가합니다. 따라서 상수 인자로 증가하는 배열 크기가 점근적 복잡성에 부정적인 영향을 미치지 않는다는 것을 이해할 수 있습니다.