使用O表示法在for循环中的LinkedList上调用get（）的复杂性

Question

我有一个通用的实践，可以使用O（）表示法确定一小段代码的复杂性。

代码是：

for (int i = 0; i < list.size(); i++)
    System.out.println(list.get(i));

有问题的列表是链接列表。对于我们的实践，我们给了现成的LinkedList类，尽管我们必须编写自己的size()和get()方法。

使我困惑的是在最终计算中该算什么。问题问：

如果列表中有100个元素，它将进行多少次查找？基于此，使用O（）表示法计算程序的复杂度。

如果我只是在计算get()方法，它将平均进行n / 2次查找，从而导致O（n）的O表示法很大。但是，for循环的每次迭代都需要重新计算size（），这涉及到查找（以确定链接列表中有多少个节点）。

在计算此代码的复杂度时，是否应考虑到这一点？还是计算大小不算作查找？

Answer 1

在Java LinkedList中，get(int)操作的复杂度为O(N)，size()操作的复杂度为O(1)。

Answer 2

我可能回答得有点晚，但是我认为这个for循环实际上是

说明

每次循环迭代时，您都将访问列表的第i个索引。因此，您的通话顺序为：

这是因为每次迭代i都会递增，而您循环n次。

因此，可以使用以下总和来评估方法调用的总数：

Answer 3

由于它是一个链表，因此确定大小将是一个 O(N) 操作，因为您必须遍历整个列表。

另外，您错误地计算了 .get() 的时间复杂度。对于 big-O 来说，重要的是最坏情况的计算。对于链表来说，最坏的检索情况是该元素位于链表的末尾，因此也是 O(N)。

总而言之，您的算法每次迭代将花费 O(2N) = O(N) 时间。我希望你能从那里弄清楚整个循环的时间复杂度是多少。

顺便说一句，在现实世界中，您只想在循环之前计算一次大小，正是因为这样效率很低。显然，如果列表的大小可以在循环期间改变，那么这不是一个选择，但对于这种非变异算法来说，情况似乎并非如此。