堆栈中的每次插入都是 O(1) ，那么插入“n”个元素所需的时间是 O(n) 吗？我们也可以对哈希表说同样的话吗？在平均情况下，在哈希表中插入“n”个元素所需的时间 = O(n) ？
问问题
6552 次
2 回答
3
是的。主要因素不是插入时间，它是恒定的，它是迭代所有你正在插入的东西所花费的时间。如果插入不是在恒定时间内发生，它会更复杂。
请注意，在 HashTable 情况下，很大程度上取决于 HashTable 是否必须自行增长或在发生这种情况时重新散列其中的所有内容，但对于简单的情况（即假设表足够大以容纳所有内容，并且您的哈希码生成不会生成碰撞）插入的上限应该是 n。
于 2011-06-15T18:46:04.163 回答
0
堆栈中的每次插入都是 O(1) ，那么插入“n”个元素所需的时间是 O(n) 吗？我们也可以对哈希表说同样的话吗？在平均情况下，在哈希表中插入“n”个元素所需的时间 = O(n) ？
正如您提到的堆栈，我假设我们使用堆栈解决哈希表中的冲突（以链接方式，使用封闭寻址）。
在这种情况下，我回答：
是的，“平均情况下，在哈希表中插入 'n' 个元素所需的时间 = O(n)”。
更加具体。在您的情况下插入哈希表是：
- 使哈希 = O(1)
- 插入使用 hash = O(1) 选择的堆栈
整个哈希插入是 O(1)。所以n 次操作是 O(n)。
我的建议：在你的考试中要非常具体地了解你的假设（你使用的结构、它们的实现和复杂性），因为所有这些细节都可能对所有方程的结果产生重大影响。
于 2012-01-09T15:57:15.667 回答