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