java - Linked List 和 ArrayList 之间的运行时间？代码分析

Question

下周我有期中考试，其中一些与代码分析/求和简化有关。我很迷茫，我试图理解我的教授在练习工作表上给我们提出的这个问题。

这是伪代码:

 List <Integer> method( List <Integer> ints) { 
     for ( int i = 0; i < ints.size() / 2; i ++) { 
         swap(i, n − i − 1);
  }

问题是:假设 List 是 ArrayList，将此方法的最坏情况运行时间表示为总和？ 其中我得到了 O(log n)，因为列表的大小每次都被分成两半。

但接下来的问题是:假设 List 是 LinkedList，将此方法的最坏情况运行时间表示为总和？ 现在我很困惑，我知道ArrayLists和LinkedLists有不同的时间复杂度，但是答案不是一样的O(log n)吗？

另外，我如何将其表示为每个问题的总和？这不是家庭作业，但我正在尽力理解这个主题。

Answer 1

如果ints是一个ArrayList，它可以在常数时间内访问任何元素。因此，它会遍历前半部分的元素，并将它们与后半部分的相应元素交换。这仍然被认为是 O(n)，因为迭代总数将为 1/2 * (n)，并且您删除了大 O 表示法的常量。

如果 ints 是一个 LinkedList，则您无法恒定时间访问任何元素 - 您必须遍历整个列表才能访问每个元素。因此，对于列表前半部分中的每个元素，您将再次迭代以从后半部分中查找相应的元素。这会导致最坏情况下的运行时间为 O(n^2)。