时间数据结构的复杂性

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-数组，应指示索引中插入或删除，因此需要做一些元件向前或向后移动