使用O表示法在for循环中的LinkedList上调用get()的复杂性 [英] Complexity of calling get() on a LinkedList in a for loop using O notation

问题描述

我有一种使用O()表示法确定一小段代码的复杂性的通用方法.

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

代码是:

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

有问题的列表是链接列表.为了我们的实际，我们给了一个现成的LinkedList类，尽管我们必须编写自己的size()和get()方法.

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.

令我困惑的是在最终计算中该算什么.问题问:

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

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

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.

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

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).

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

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

推荐答案

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

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

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

Also, you miscalculated the time complexity for .get(). For big-O, what matters is the worst case computation. 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).

总而言之，您的算法每次迭代将花费O(2N)= 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.

顺便说一句，在现实世界中，您只想在循环之前计算一次大小，这恰恰是因为它可能效率很低.显然，如果列表的大小可以在循环期间更改，则这不是一个选择，但这种非变异算法似乎不是这种情况.

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.

这篇关于使用O表示法在for循环中的LinkedList上调用get()的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！