A Dynamic Array (abbreviated as DArray) is a type of array that permits the insertion and deletion of elements at the end to dynamically adjust its size. DArray maintains three crucial attributes, including the underlying array , the logical data size , and the actual array capacity . The invariant holds at any given moment. The operation appends the element to the end of . In case , it triggers a call to before appending , where allocates a new and larger array, moves all the data to it, increases the value of , sets up , and finally frees the old array. Two implementations of are provided: increases by a constant (e.g., 10) while doubles each time.
To initialize DArray , we set , , and allocate a size 1 array to . Assuming that both allocating and freeing arrays of length take time, and moving a single element takes time, please select the correct description(s) below.
參考答案與解析
答案 (D):ResizeB 每次容量翻倍,用攤還分析(記帳法或位能法)可證明 Insert 的攤還成本是 O(1),這是動態陣列最經典的結果。(C) 錯:ResizeA 每次只固定增加常數(如10),代表每插入約10個元素就要搬移一次目前全部資料,n 次插入總成本是 Θ(n²),攤還下來是 Θ(n) 而非 O(1)。(A) 錯:陣列搬移不影響「目前這個陣列」的隨機存取,動態陣列本來就是為了支援 O(1) 隨機存取而設計的。(B) 錯,這是過度絕對的說法。(E) 錯:把縮小門檻設在「剩一半」會造成插入/刪除反覆觸發搬移的震盪問題,破壞 O(1) 攤還界線(同一個陷阱,不論搭配 ResizeA 或 ResizeB 都一樣)。