堆棧/隊列中鏈接列表/雙向鏈表的複雜性？

堆棧（LIFO）情況：如果我在鏈表中使用peek（）命令，則複雜度爲0（n）。爲什麼會這樣，因爲我只讀了列表的最後一個對象？它應該是0（1）嗎？在隊列（FIFO）中：如果我在鏈表中使用peek（），複雜度現在爲0（1）。爲什麼會有差異？堆棧/隊列中鏈接列表/雙向鏈表的複雜性？

感謝您花時間閱讀和幫助。

來源

2017-03-22 Someonewhohaveacat

您確定複雜嗎？訪問堆棧的頂層元素是0（1），對於像push（）和pop（）這樣的所有操作來說，它們與堆棧的大小無關。

如果您想要訪問堆棧的底部，您將得到0（n）（因爲您需要從頂部元素開始逐個元素）。

你從哪裏得到這種複雜性？

來源

2017-03-22 19:55:31

我從我的老師那裏瞭解到了這一點。我再次問他。他說這是對的。我請求解釋，但我不明白。這就是爲什麼我把它帶到這裏...... – Someonewhohaveacat

我能想出的唯一解釋是peek（）實際上是一個可以在堆棧中找到任何元素的搜索。在那種情況下，正如我所提到的那樣，當你從頂部開始並且以元素線性查看堆棧時，該操作的複雜度將是O（n）。但是，您應該始終能夠直接訪問堆棧的頂部。這是一個比較各種結構的操作複雜性的有趣的文章：http://stackoverflow.com/questions/7294634/what-are-the-time-complexities-of-various-data-structures –

此外，我建議你檢查這也是：http://bigocheatsheet.com/ 和在這裏：https://en.wikipedia.org/wiki/Peek_(data_type_operation）希望有所幫助。 –

堆棧/隊列中鏈接列表/雙向鏈表的複雜性？

回答

相關問題