java - 验证涉及 LinkedList 的 3 个循环的 Big-O

Question

在大约 7 小时内进行一次考试，并在我们的教练给我们的练习考试中提出这个问题。我在算法分析方面很可怕，因为我还没有足够的练习，而且导师也没有解释得很好。

下面是问题，每个问题的右侧是我认为循环的顺序。以下是我选择订单的原因：

a.) 每次调用 get() 时，必须从列表的前面或后面开始搜索（因为 LinkedList 是一个双链表。我们并没有真正讨论 LinkedList，我们只是创建了自己的 DLL和 SLL，所以我对 LinkedList 的熟悉程度并不是那么好）。

b.) 对 hasNext 的调用是 O(1) 并且在 while 循环内仅将迭代器从其当前位置推进（不必每次都从前面开始）。因此，它只横穿列表一次。

c.) 与 b 相同，因为 for-each 循环的工作方式与 b 中代码的工作方式完全相同。

无论如何，希望有人可以为我确认这些，如果它们不正确，请告诉我原因。

谢谢你。

标签： java

Answer 1

他们是对的！！原因和你提到的一样。