最常见的数据结构是什么，以及对它们进行操作的主要目标是什么？

Question

我正在努力掌握大O符号。它看起来很抽象。我选择了最常见的数据结构--数组、哈希表、链表(单链表和双链表)和二叉树，并猜测了最常见的操作--插入和搜索--的大O符号。这是一个惯性视图的准备工作。我只需要学习基础知识，而不是阅读一整本关于算法的教科书，尽管这将是理想的。下表是否有效？

Data Structure       Big O Search   Big O Insert
Array                    O(1)          O(n)
Hash                     O(1)          O(1)
Single Linked List       O(n)          O(1)
Double Linked List       O(n)          O(1)
Tree                   O(log n)      O(log n)

Answer 1

对于Array，获取/返回一个元素需要O(1)，但是搜索一个元素应该需要O(n)。对于树，我假设你指的是balanced二进制搜索树。

Answer 2

对于散列插入，记住O(1)是最优的。如果您的哈希表接近满，您的效率将接近O(n)。

此外，对于按对数排序的数组，搜索时间为O( n)。