什么是索引的时间复杂度，插入和常用数据结构去除？(What is the time complexi

没有可供操作的大O符号上最常见的数据结构，包括数组，链表，哈希表等的汇总

Answer 1:

有关这个主题的资料可在维基百科上的：搜索数据结构

+----------------------+----------+------------+----------+--------------+
|                      |  Insert  |   Delete   |  Search  | Space Usage  |
+----------------------+----------+------------+----------+--------------+
| Unsorted array       | O(1)     | O(1)       | O(n)     | O(n)         |
| Value-indexed array  | O(1)     | O(1)       | O(1)     | O(n)         |
| Sorted array         | O(n)     | O(n)       | O(log n) | O(n)         |
| Unsorted linked list | O(1)*    | O(1)*      | O(n)     | O(n)         |
| Sorted linked list   | O(n)*    | O(1)*      | O(n)     | O(n)         |
| Balanced binary tree | O(log n) | O(log n)   | O(log n) | O(n)         |
| Heap                 | O(log n) | O(log n)** | O(n)     | O(n)         |
| Hash table           | O(1)     | O(1)       | O(1)     | O(n)         |
+----------------------+----------+------------+----------+--------------+

 * The cost to add or delete an element into a known location in the list (i.e. if you have an iterator to the location) is O(1). If you don't know the location, then you need to traverse the list to the location of deletion/insertion, which takes O(n) time. 
** The deletion cost is O(log n) for the minimum or maximum, O(n) for an arbitrary element.

Answer 2:

我想我会开始你关闭一个链表的时间复杂度：

索引----> O（n）的
插入/在端删除----> O（1）或O（n）的
插入/在中间删除---> O（1）以迭代为O（n）与出

在结束时插入的时间复杂度取决于如果你有最后一个节点的位置，如果你这样做，这将是O（1）其他明智的您将不得不通过链接列表和时间复杂度将上升至O搜索（N）。

Answer 3:

请记住，除非你正在写自己的数据结构（C语言如链表），它可以显着的数据结构中选择你的语言/框架的实现依赖。作为一个例子，看看在苹果CFArray过的可笑鱼基准。在大约30,000对象从线性时间变化的恒定时间 - 在这种情况下，数据类型，从苹果公司的CoreFoundation框架CFArray，取决于有多少对象数组中实际上是实际上改变了数据结构。

这实际上是关于面向对象编程美丽的事情之一-你不需要知道它是如何工作的，只是它的工作原理，以及“它是如何工作”可以根据需求的变化。