您在问题中链接到的页面有许多数据结构的列表。每一个页面都详细介绍了特定的数据结构。我知道您想要现成格式的比较表，但由于它似乎不存在，因此您可以通过浏览各个页面轻松地将其组合在一起。例如，此处给出了数组中各种算法的比较，并且对于 b -tree 此处。因此，可能需要一些工作才能将其全部编译成一个简单的参考。嗯……也许正在制作一篇博客文章。
The page that you linked to in your question has a list of many data structures. Each of them a page that details the specific data structures. I know you want the table of comparisons in a ready made format but since it does not appear to exist then it might be something that you can put together easily by browsing through the various pages. For instance the comparison of the various algorithms in the array is given here, and for the b-tree here. So it may require some work to compile it all into a simple reference. Hmmm...maybe there is a blog post in the making.
+----------------------+----------+------------+----------+--------------+
| | 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.
+----------------------+----------+------------+----------+--------------+
| | 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.
发布评论
评论（2）
您在问题中链接到的页面有许多数据结构的列表。每一个页面都详细介绍了特定的数据结构。我知道您想要现成格式的比较表，但由于它似乎不存在，因此您可以通过浏览各个页面轻松地将其组合在一起。例如，此处给出了数组中各种算法的比较，并且对于 b -tree 此处。因此，可能需要一些工作才能将其全部编译成一个简单的参考。嗯……也许正在制作一篇博客文章。
The page that you linked to in your question has a list of many data structures. Each of them a page that details the specific data structures. I know you want the table of comparisons in a ready made format but since it does not appear to exist then it might be something that you can put together easily by browsing through the various pages. For instance the comparison of the various algorithms in the array is given here, and for the b-tree here. So it may require some work to compile it all into a simple reference. Hmmm...maybe there is a blog post in the making.
这是维基百科上的内容：数据结构的最坏情况分析
Here it is on Wikipedia: Worst-case analysis of data structures