不同集合实现的时间复杂度和内存需求
Time complexity and memory requirements of different set realizations
我想练习一下数据结构。假设我有一个（动态数组、链表、双向链表、搜索树、散列table）。所以我在想
- 它们中哪一个需要最少的内存。我会说这是一个哈希 table
- 哪个实现在查找值时需要O(log N)的时间复杂度。我会说这是一棵搜索树。
- 哪个实现通常是suitable实现一个序列。链表？
我只是在检查自己，只是想知道我是否有任何想法是错误的。提前谢谢你。
最小内存量：它是 linked-list 或 BST，因为它们只占用所需的确切内存，而其他数据结构可能分配比实际使用的内存更多的内存。双 linked 列表类似于 linked 列表，但 link“返回”需要更多内存。
不确定你所说的“实现”是什么意思，事实上 BST 中的搜索时间是 O(log N) 假设树是平衡的，这是一个重要的假设！
同样，不清楚什么是实现或什么是序列。假设 list/array 是有序的，那么遍历它们确实是最有效的。再一次，这是一个重要的假设！
我想练习一下数据结构。假设我有一个（动态数组、链表、双向链表、搜索树、散列table）。所以我在想
- 它们中哪一个需要最少的内存。我会说这是一个哈希 table
- 哪个实现在查找值时需要O(log N)的时间复杂度。我会说这是一棵搜索树。
- 哪个实现通常是suitable实现一个序列。链表？
我只是在检查自己，只是想知道我是否有任何想法是错误的。提前谢谢你。
最小内存量：它是 linked-list 或 BST，因为它们只占用所需的确切内存，而其他数据结构可能分配比实际使用的内存更多的内存。双 linked 列表类似于 linked 列表，但 link“返回”需要更多内存。
不确定你所说的“实现”是什么意思，事实上 BST 中的搜索时间是 O(log N) 假设树是平衡的，这是一个重要的假设！
同样，不清楚什么是实现或什么是序列。假设 list/array 是有序的，那么遍历它们确实是最有效的。再一次，这是一个重要的假设！