Rob*_*ers 2 arrays big-o data-structures
根据Wikipedia关于动态数组的文章,在数组末尾插入/删除是O(1),而从中间插入/删除是O(n).究竟是为什么呢？
另外 - 如果我有一个包含5个元素的动态数组,并且我在第6位插入一个新元素,则操作为O(n),而如果我使用该函数追加到数组的末尾则为O(1).假设数组在任何一种情况下都不需要调整大小,这不是相同的操作吗？或者附加到动态数组是否真的在位置6之外的某处插入新元素？
谢谢!
编辑:我认为我的主要困惑是在数组末尾插入和插入相当于数组末尾的特定位置之间的区别.
我想一个指向数组末尾的内存地址的指针保持方便,这就是追加操作很快的原因.相反,如果我指定一个精确的位置(即使它是数组的末尾),它也不会知道在那个位置插入等于使用前面提到的内存地址所以它必须遍历整个数组,是吗？
pax*_*blo 10
要插入数组的末尾,只需将项目放在那里即可.
要插入到数组的中间,您需要将该点之后的项目向上移动一个.
要从数组的末尾删除,只需将其计数减一.
要从中间删除,您必须执行此操作并将其他项目向下移动.
正是这种转变将其变为O(n).
数量级完全取决于"动态阵列"实际上是什么类型的数据结构("动态阵列"不是严格定义的数据结构,它更多是通过采用特定数据结构实现的期望结果).您给出的示例将通过使用链接列表实现的动态数组反映.如果列表结构保留指向最终元素的指针,则添加到最后可以是O(1).插入(无论索引如何)将需要遍历链表,这意味着每个节点一个操作直到所需的索引.
| 归档时间： |
|
| 查看次数： |
3099 次 |
| 最近记录： |