英文:
Why is the runtime for this code O(N^2) when using a linked list?
问题
这里是你要求的代码翻译部分：
所以，关于数据结构，这里有一段我们需要找到运行时的代码：
public static int calc(List<Integer> lst) {
int count = 0;
int N = lst.size();
for (int i = 0; i < N; i++) {
if (lst.get(i) > 0)
sum += lst.get(i);
else
sum += lst.get(i) * lst.get(i);
}
return sum;
}
我们需要回答的是，如果lst是一个LinkedList和一个ArrayList时，运行时分别是多少。对于数组来说很简单，只是O(N)，因为它循环遍历列表并检查每个元素，而lst.get(i)是一个常数时间的操作，因为它是一个数组。棘手的部分在于链表。从我所看到的情况来看，每次在链表上调用lst.get(i)时，它都必须从链表头开始遍历到索引i。从这段代码中看，它似乎会根据if语句的结果调用get方法3次或2次，所以我认为它的运行时会是O(N^4) / O(N^3)。然而，根据一个研究生的说法，这个时间复杂度是O(N^2)。只是想知道是否有人能解释正确的答案以及原因。
我在Java上运行了一些测试代码，得到了以下时间结果：
列表1是元素0到99，大小为100。列表2是元素0到9999，大小为10000。
列表一用时2868毫秒，列表二用时99443毫秒。
英文:
So, for data structures here is a piece of code we are supposed to find the runtime for:
public static int calc( List<Integer> lst )
{
int count = 0;
int N = lst.size();
for ( int i=0; i<N; i++)
{
if (lst.get(i) > 0)
sum += lst.get(i);
else
sum += lst.get(i) * lst.get(i);
}
return sum;
}
We are supposed to answer what the runtime would be if lst is a LinkedList vs an ArrayList. So for an array it is pretty easy, just O(N) because it loops through the list checking every element, and lst.get(i) is a constant time operation since it is an array. The tricky part is over a linked list. From what I'm seeing, every time lst.get(i) would be called on a linked list, it would have to start at the head of the list and traverse to index i. And from this code it looks like it would call get either 3 times or 2 times depending on the result of the if statement, so I would think it would be O(N^4) / O(N^3) runtime. However, according to a grad student, it is O(N^2) time. Just wondering if someone can explain what the correct answer is and why.
I ran some test code on java and got this as my time result:
list 1 is elements 0 - 99 of size 100. And list 2 is elements 0 - 9999, of size 10,000
List one finished in 2868 ms, list two finished in 99443 ms.
答案1
得分: 2
以下是翻译好的部分：
对于每次循环迭代，最多有3次获取操作。对于LinkedList来说，获取操作的时间复杂度是O(N)，因为你必须遍历整个链表。因此，最坏情况下有3 * O(N)次操作，最坏情况下重复了N次。因此，时间复杂度为O(N^2)。
然而，通过使用增强型for循环，可以使得针对LinkedList的效率与ArrayList一样高，而且更简单：
for (int e : lst) {
if (e > 0)
sum += e;
else
sum += e * e;
}
这在内部使用了一个Iterator，对于LinkedList的每个元素查找并不是O(N)，因为它会跟踪当前位置：从Iterator获取下一个元素只需要O(1)的时间。
英文:
There are at worst 3 get operations for every loop iteration. For LinkedList, a get operation is O(N) because you have to walk the list. As such, there at worst 3 * O(N) operations, at worst N times. Hence, O(N^2).
However, it can be made as efficient for LinkedList as ArrayList - and simpler - by using an enhanced for loop:
for (int e : lst) {
if (e > 0)
sum += e;
else
sum += e * e;
}
This internally uses an Iterator, which isn't O(N) to look up each element for LinkedList, because it keeps track of where it is: getting the next element from the Iterator is just O(1).
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论