時間數據結構的複雜性

Question

我去了this page：

而且我有以下問題：

1. 不插入和刪除該表中的意思是插入和刪除在僅結束？

2. 對於基本數組，爲什麼插入和刪除的平均值和最壞情況標記爲-？

3. 表中的索引是什麼意思？這是否意味着訪問？

4. 爲什麼插入和刪除動態數組O（n）？

5. 爲什麼鏈接列表O（n）與動態數組O（1）的索引是？這是因爲動態數組是連續的，可以通過指針算術直接訪問，而對於鏈接列表則需要線性搜索？

Answer 1

1. 不插入，並在此表中刪除意味着只在末尾插入和刪除？

   那些反映隨機插入和刪除。

---

對於基本陣列，爲什麼插入和刪除對平均和最壞的情況下被標記爲-？

因爲「基本數組」是一個靜態數組結構。您不能插入或刪除元素。

---

什麼索引表中的是什麼意思？這是否意味着訪問？

這意味着：通過索引（位置）訪問，而不是通過密鑰訪問。

---

爲什麼插入和動態陣列爲O（n）的刪除？

因爲插入/刪除可能需要數組長度增長或縮小。這可能涉及複製（全部）元素。因此O（N）。

---

爲什麼是鏈表O（n）的索引，而動態陣列的O（1）？這是因爲動態數組是連續的，可以通過指針算術直接訪問，而對於鏈接列表則需要線性搜索？

是的。

Answer 2

對於如圖4所示，當插入或刪除元素中或從一個d-數組，應指示索引中插入或刪除，因此需要做一些元件向前或向後移動