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

问题描述

我有一个 uni 实用程序可以使用 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屋！