我有一个 uni 实用程序，可以使用 O() 表示法确定一小段代码的复杂性。
代码是:
for (int i = 0; i < list.size(); i++)
System.out.println(list.get(i));
所讨论的列表是一个链表。对于我们的实践，我们得到了一个现成的 LinkedList 类，尽管我们必须编写自己的 size() 和 get() 方法。
这个问题让我很困惑的是最后计算要算什么。问题是:
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()，这涉及到查找(以确定链表中有多少个节点)。
在计算这段代码的复杂度时，是否应该考虑到这一点？还是计算大小不算查找？
最佳答案
我回答可能有点晚，但我认为这个 for 循环实际上是 
解释
您将访问列表的第 i 个索引的每个循环迭代。因此，您的调用顺序为:
这是因为每次迭代 i 都会递增，并且您正在循环 n 次。
因此，可以使用以下总和来评估方法调用的总数:
关于java - 使用 O 表示法在 for 循环中的 LinkedList 上调用 get() 的复杂性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15192581/