使用链表在堆栈中插入n个元素的时间复杂度是多少？
堆栈中的每次插入都是 O(1)，那么插入“n”个元素所需的时间是 O(n) 吗？ 我们可以对哈希表进行类似的讨论吗？在平均情况下，在哈希表中插入“n”个元素所需的时间 = O(n) ？
Each insertion in a stack is O(1) so is the time taken to insert 'n' elements O(n) ?
Can we speak similarly for a hash-table as well ? In average case the time taken to insert 'n' elements in a hash table = O(n) ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
是的。主导因素不是插入时间，插入时间是恒定的，而是迭代所有要插入的内容所需的时间。如果插入不是在恒定时间内发生，情况会更复杂。
请注意，在 HashTable 情况下，很大程度上取决于 HashTable 是否必须自行增长或在发生这种情况时重新散列其中的所有内容，但对于简单的情况（即假设表足够大以容纳所有内容，并且您的哈希码生成不会生成碰撞）插入的上限应该是 n。
Yes. The dominating factor is not the insert time, which is constant, its the time it takes to iterate over all the things you are inserting. If inserting did not happen in constant time, it would be more complicated.
Note that in the HashTable case a lot depends on if the HashTable has to grow itself or rehash everything in it when that happens, but for the simple case (i.e. assuming the table is big enough to hold everything, and your hashcode generation does not generate collisions) the upper bound on insert should be n.
正如您提到的 stack ，我假设我们使用 stack 解决哈希表中的冲突（以链接方式，使用封闭寻址）。
在这种情况下，我回答：
是的，“平均情况下在哈希表中插入'n'个元素所需的时间 = O(n)”。
更具体地说。在您的情况下插入到哈希表是：
整个哈希插入是 O(1)。因此 n 次操作的时间复杂度为 O(n)。
我的建议：在考试中要非常具体地说明您的假设（您使用的结构、它们的实现和复杂性），因为所有这些细节可能会对所有方程的结果产生重大影响。
As you mentioned stack , I assume we resolve collisions in hashtable using stack (in chaining manner, using closed addressing ).
In such case I answer:
Yes, "average case the time taken to insert 'n' elements in a hash table = O(n)".
To be more specific. As inserting to hash table in your case is :
Whole hash insertion is O(1). So n operations is O(n).
My advice : be very specific on your exam about your assumptions (structures you use, their implementation and complexity) as all those details might have significant impact on result of all equations.