java 使用 O 表示法在 for 循环中的 LinkedList 上调用 get() 的复杂性

Complexity of calling get() on a LinkedList in a for loop using O notation

提问by Andrew Martin

I've a uni practical to determine the complexity of a small section of code using the O() notation.

我有一个 uni 实用程序来使用 O() 表示法确定一小段代码的复杂性。

The code is:

代码是：

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

The list in question is a linked list. For our practical, we were given a ready made LinkedList class, although we had to write our own size()and get()methods.

有问题的列表是一个链表。对于我们的实际，我们得到一个现成的LinkedList类，虽然我们不得不写我们自己size()和get()方法。

What is confusing me about this question is what to count in the final calculation. The question asks:

这个问题让我困惑的是在最终计算中计算什么。问题问：

How many lookups would it make if there 100 elements in the list? Based on this, calculate the complexity of the program using O() notation.

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

If I am just counting the get()method, it will make an average of n/2 lookups, resulting in a big O notation of O(n). However, each iteration of the for loop requires recalculating the size(), which involves a lookup (to determine how many nodes are in the linked list).

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

When calculating the complexity of this code, should this be taken into consideration? Or does calculating the size not count as a lookup?

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

采纳答案by jrajav

Since it is a linked list, to determine the size will be an O(N) operation, since you must traverse the whole list.

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

Also, you miscalculated the time complexity for .get(). For big-O, what matters is the worst casecomputation. For a linked list, the worst case of retrieval is that the element is at the end of the list, so that is also O(N).

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

All told, your algorithm will take O(2N) = O(N) time per iteration. I hope you can go from there to figure out what the time complexity of the whole loop will be.

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

By the way, in the real world you would want to compute the size just once, before the loop, precisely because it can be inefficient like this. Obviously, that's not an option if the size of the list can change during the loop, but it doesn't look like that's the case for this non-mutating algorithm.

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

回答by

I might be bit late to answer, but I think this for loop would actually be

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

Explanation

解释

Each loop iteration you would be accessing the ith index of the list. Your call sequence would therefore be:

每次循环迭代您将访问列表的第 i 个索引。因此，您的调用顺序将是：

This is because each iteration iis incremented, and you are looping ntimes.

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

Therefore, the total number of method calls can be evaluated using the following sum:

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

回答by Sahin Habesoglu

In Java LinkedList, get(int) operation is O(N), and size() operation is O(1) complexity.

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

回答by Eduardo macedo

Short answer: It depends on the interpretation of the question.

简短回答：这取决于对问题的解释。

If the question is asking how many times I will have to jump the list if I want to find 100th position (like calling .get(100)), the complexity would be O(N)since I need to go through the entire list once.

如果问题是问如果我想找到第 100 个位置（例如调用.get(100)），我将不得不跳转列表多少次，那么复杂性将是O(N)，因为我需要遍历整个列表一次。

If the question is asking for the complexity of finding an ith variable by checking each index ( like .get(1), .get(2), ..., .get(100)), the complexity would be O(N2)as explained by michael.

如果问题是通过检查每个索引（如.get(1), .get(2), ..., .get(100)）来询问找到第 i 个变量的复杂性，那么复杂性将是O(N2)，正如 michael 所解释的那样。

Long answer:

长答案：

The complexity of calculating the size depends on your implementation. If you traverse the entire list to find the size, the complexity would be O(N)for the size calculation (and O(2N)in the first case, O(N2 + N)in the second) <- this last part also depends on your implementation as I'm thinking you're calculating the size out of the for-loop.

计算大小的复杂性取决于您的实现。如果您遍历整个列表以查找大小，则大小计算的复杂度将为O(N) （第一种情况下为O(2N)，第二种情况下为O(N2 + N)）<-这最后一部分也是取决于您的实现，因为我认为您正在计算 for 循环之外的大小。

if you have the size saved as an instance variable that gets bigger every time an element is added, you'll have O(1)for the size and the same complexity for first and second case.

如果您将大小保存为每次添加元素时都会变大的实例变量，那么大小将是O(1)并且对于第一种和第二种情况具有相同的复杂性。

The reason why we round O(2N)(or any case of O(aN + b)) to O(N)is because we care only about the growth of time spent to process the data. If N is small, the code would run fast anyways. If N is big, the code might run in a lot more time depending of the complexity but the constants a and b wouldn't be of much effect when compared with a worse complexity implementation.

我们将O(2N)（或任何O(aN + b) 的任何情况）舍入为O(N)的原因是因为我们只关心处理数据所花费的时间的增长。如果 N 很小，代码无论如何都会运行得很快。如果 N 很大，则代码可能会运行更多时间，具体取决于复杂性，但与更差的复杂性实现相比，常量 a 和 b 不会有太大影响。

Suppose a code runs in 2 seconds for a small input N in O(N) complexity.
as the value gets bigger: N, 2N, 3N, 4N, ..., kN
if the code has complexity O(N)the time would be: 2, 4, 6, 8, ..., 2k
if the code has complexity O(2N)the time would be: 4, 8, 12, 16, ..., 2k * 2
if the code has complexity O(N2)the time would be: 4, 16, 36, 64, ..., (2k)2

假设对于 O(N) 复杂度的小输入 N，代码在 2 秒内运行。
随着值变大： N, 2N, 3N, 4N, ..., kN
如果代码的复杂度为O(N)时间将是： 2, 4, 6, 8, ..., 2k
如果代码有复杂度O(2N)时间为：4, 8, 12, 16, ..., 2k * 2
如果代码的复杂度为O(N2)时间为：4, 16, 36, 64, ... , (2k)2

As you can see the last implementation is getting out of hand really fast while the second is only two times slower than a simple linear. So O(2N) is slower but it's almost nothing compared to a O(N2) solution.

正如您所看到的，最后一个实现非常快地失控，而第二个仅比简单的线性慢两倍。所以 O(2N) 较慢，但与 O(N2) 解决方案相比，它几乎算不了什么。