使用鏈接列表在堆棧中插入n個元素的時間複雜度是多少？

Question

堆棧中的每個插入是O（1），插入'n'個元素O（n）所需的時間也是如此？ 我們可以說類似的哈希表嗎？在平均情況下，將'n'元素插入散列表中的時間= O（n）？

Answer 1

是的。主導因素不是插入時間，它是不變的，它是迭代你插入的所有東西所花費的時間。如果插入不是在一定時間內發生的話，那將會更加複雜。

請注意，在HashTable的情況下，很大程度上取決於HashTable是否必須自己增長或重新哈希它發生時的所有內容，但對於簡單情況（即假設表足夠大以容納所有內容，並且您的哈希碼代不會產生衝突）插入的上限應該是n。

Answer 2

堆棧中的每個插入是O（1），插入'n'個元素O（n）所需的時間是多少？ 我們可以說類似的哈希表嗎？在平均情況下，花費在 之上的時間在散列表中插入'n'個元素= O（n）？

至於你提到堆棧，我假設我們使用棧（in chaining manner, using closed addressing）解決哈希表衝突。

在這種情況下，我回答：

是「平均情況所花費的時間來插入‘n’個在哈希表中的元素= O（N）」。

更具體一點。作爲插入到哈希表中的情況下是：

• 使得散列= O（1）
• 插入與散列選擇的堆棧= O（1）

所有散列插入是O（1 ）。所以n操作是O（n）。

我的建議：對您的假設（您使用的結構，它們的實施和複雜性）進行非常具體的檢查，因爲所有這些細節都可能對所有方程的結果產生重大影響。