最常见的数据结构和对其进行操作的 Big O 是什么？
我正在尝试掌握大 O 符号。看起来很抽象。我选择了最常见的数据结构 - 数组、哈希、linkedl 列表（单和双）和二叉搜索树，并对最常见操作的 Big 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)
I am trying to get a grasp on Big O notations. It seems pretty abstract. I selected the most common data structures - array, hash, linkedl list (single and double) and a binary search tree and guessed somewhat at the Big O notation for the most common operatons - insert and search. This is preparation for an inerview. I need to learn just the basics not read a whole text book on algorithms though this would be ideal. Is the table below valid?
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)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
对于数组，获取/返回一个元素需要 O(1)，但搜索一个元素需要 O(n)。
对于树，我假设您指的是平衡二叉搜索树。
For Array, to get/return an element takes O(1), but to search for an element should take O(n).
For Tree, I assume that you meant balanced binary search tree.
对于哈希插入，请记住 O(1) 是最佳的。如果你的哈希表接近满，你的效率将接近 O(n)。
另外，对于排序数组，搜索的时间复杂度为 O(log n)。
For hash inserts, remember that O(1) is optimal. If your hash table is close to full, your efficiency will approach O(n).
Also, for a sorted array, searching is O(log n).