我对哪个选项是正确的以及为什么感到困惑。所以这里有一些问题：
-
将节点从单链表中的最后一个位置删除的最佳运行时间是多少。
- (a) O(1)
- (b) Ω(n)
- (c) O(log n)
- (d) θ(n2)
我的想法：
我认为b中的解决方案？因为，我知道当你删除链表的最后一个元素时，它是O(n)，因为你必须遍历链表的所有元素。 -
将元素推送到双链表中实现的堆栈的最坏运行时间是多少？
- (a) O(1)
- (b) 问(8)
- (c) O(n log n)
- (d) Ω(n)
我的想法：
我认为解决方案是d，因为将元素插入链表的大Oh是O(n)，其中n是要插入的元素数。
我对这个话题真的很困惑，如果有人可以修改我的解决方案并理解为什么他们的解决方案是正确的，那么我将不胜感激。谢谢。
第一个你是对的。为了删除最后一个元素，您需要遍历列表并修改那里的指针，使其为 Ω(n)。
然而，在第二个中，它是O(1)。堆栈是后进先出。您有一个指向堆栈头部的指针。您需要做的就是为新元素创建一个节点，使其成为下一个当前头部，并将头部设置为新创建的头部。因此，操作数不是堆栈大小的函数。它可以在恒定时间内完成，即 O(1)。
编辑：上面的答案假设数据结构没有用一些数组实现，由于调整大小，这些数组可能再次是O(n)。