amortized analysis
-
알고리즘 ch 6 array doubling학교 수업/알고리즘 2020. 6. 14. 20:02
Dynamic Sets and Searching Array Doubling - 배열의 크기를 늘려야 할 때 원래 배열의 2배 크기를 할당 받아 원래의 배열에 있던 값들을 옮기는 작업. - 값을 하나 옮길 때 t시간이 덜린다고 하면, size n의 배열에 n+1번째 값이 들어올 때 2n개의 새로운 메모리를 할당 받아 n개의 값들을 옮기고 n+1번째의 원소를 입력해야 한다. 이 작업에는 기존 n개의 원소를 옮길 때 t*n의 시간이 필요할 것이다. 그럼 이 작업을 포함해 이전의 총 이동 시간을 생각해보면 t*n + t*n/2 + t*n/4 + ... = t(n + n/2 + n/4 + 1) 의 시간이 걸렸을 것이며 이는 총 2t*n보다는 적게 걸렸을 것이다. Array doubling이 중요한 이유는 1개의 ..