3
要在DLL（雙向鏈表）整個列表中插入/刪除一個具有特定值的節點，需要通過遍歷來查找位置，因此這些操作應該是O（n）。在O（n）的雙向鏈表中插入/刪除的時間複雜度是多少？
如果是這種情況，那麼怎麼來STL列表（最有可能使用DLL實現）能夠在固定時間提供這些操作？
謝謝大家對我說清楚。
A
回答
12
插入和刪除在已知位置是O（1）。然而，找到那個位置是O（n），除非它是列表的頭部或尾部。
當我們談論插入和刪除複雜性時，我們通常假設我們已經知道將會發生什麼。
1
刪除一個任意值（而不是一個節點）確實是O（n），因爲它需要找到這個值。刪除一個節點（即當你開始瞭解節點時）是O（1）。
基於值插入 - 例如，插入排序的列表 - 將是O（n）。如果您在現有已知節點之後或之前插入O（1）。
插入到列表的頭部或尾部將始終爲O（1） - 因爲這些只是上述的特例。
2
不是。 STL方法將迭代器帶到要插入的位置，所以嚴格來說，它們是O(1)，因爲您在給它們定位。但是，您仍然必須自己在O(n)中找到自己的位置。
相關問題
- 1. 雙向鏈表中節點刪除的時間複雜度
- 2. 時間複雜度：O（logN）或O（N）？
- 3. 爲什麼鏈表刪除和插入操作的複雜度爲O（1）？它不應該是O（n）
- 4. 優先級隊列O（n）的分類列表實現的插入時間複雜度是多少？
- 5. 時間複雜度O（N日誌（log n）的）+ N O（L）
- 6. 以下程序的時間複雜度是多少？ O（log n）是否正確？
- 7. 使用鏈接列表在堆棧中插入n個元素的時間複雜度是多少？
- 8. 下面的代碼片段O（n^2）的時間複雜度是多少？
- 9. 時間複雜度 - O（n^2）到O（n log n）搜索
- 10. SQL - 外鍵O（1）的時間複雜度是多少？
- 11. Collection.toArray（）的時間複雜度是多少？
- 12. unordered_set <int> :: iterator it + n的時間複雜度是多少？
- 13. 具有O（n）時間複雜度的N皇后的解釋？
- 14. 雙向搜索的時間複雜度
- 15. 是這個算法的漸近時間複雜度O（log n）？
- 16. 如何表示Big O（n！）for循環的時間複雜度？
- 17. 替代O（N^2）的時間與O（1）空間複雜度的複雜度在陣列
- 18. 大O符號中下列代碼的時間複雜度是多少？
- 19. 單鏈表中的時間複雜度
- 20. 如何確定的時間複雜度爲O（M + N）或O（Math.max（M，N））
- 21. 計數排序O（n + k）時間複雜度是什麼k？
- 22. 二叉樹O（n）的InOrder樹遍歷的時間複雜度？
- 23. 複雜度O（log（n））是否等於O（sqrt（n））？
- 24. 將元素插入此結構的分期時間複雜度是多少？
- 25. 2^N數組插入排序的時間複雜度？
- 26. 將地圖轉化爲鏈接列表的時間複雜度是多少
- 27. 我的代碼中的時間複雜度是多少
- 28. 爲什麼代碼O（log n）的時間複雜度？
- 29. a + b = O（n^2）的時間複雜度？
- 30. 以下代碼的時間複雜度如何爲O（n）？
+1 - *除非它是列表的頭部或尾部。* - 它也是O（1）找到列表中的第二個位置。第3位... – 2010-10-10 07:47:56
通過歸納，在列表中找到位置n是O（1）... heywaitaminute！ ：p – Edmund 2010-10-10 09:08:09