Array Doubling

* 우리는 계산할때 배열이 얼마나 필요한지 모른다.

* 새로운 원소를 삽입할때 room 이 필요하다면

- 두배의 길이 배열을할당한다.

- 새로운 배열로 값을 옮긴다


* t를 배열을 옮기는데 사용되는 cost 라고 하자.

- (n+1)을 삽입할때 doubling 이 발생한다고 하자.

-t*n의 시간이 걸린다  array-doubling 에

- t*n/2 + t*n/4 + t*n/8 + ... for previous array doubling

- 이것들은 t*n 보다 작다.

- total cost < 2t*n

+ Recent posts