使用O表示法在for循环中的LinkedList上调用get（）的复杂性
我可以使用O（）表示法来确定一小段代码的复杂性。
代码是：
for (int i = 0; i < list.size(); i++) System.out.println(list.get(i)); 有问题的列表是一个链表。 对于我们的实际，我们得到了一个现成的LinkedList类，虽然我们必须编写自己的size()和get()方法。
让我对这个问题感到困惑的是在最终计算中要算什么。 问题是：
如果列表中有100个元素，它会进行多少次查找？ 基于此，使用O（）表示法计算程序的复杂性。
如果我只计算get()方法，它将平均进行n / 2次查找，从而产生O（n）的大O符号。 但是，for循环的每次迭代都需要重新计算size（），这涉及查找（以确定链表中有多少个节点）。
在计算此代码的复杂性时，是否应该考虑这一点？ 或者计算大小不算作查找？
由于它是一个链表，确定大小将是一个O（N）操作，因为你必须遍历整个列表。
此外，您错误地计算了.get（）的时间复杂度。 对于big-O来说，重要的是最糟糕的情况计算。 对于链表，最糟糕的检索是元素位于列表的末尾，因此也是O（N）。
总而言之，您的算法每次迭代将花费O（2N）= O（N）时间。 我希望你能从那里找出整个循环的时间复杂度。
顺便说一句，在现实世界中，你只想在循环之前计算一次大小，正是因为它可能效率低下。 显然，如果列表的大小可以在循环期间发生变化，那么这不是一个选项，但它看起来不像这种非变异算法的情况。
在Java LinkedList中，get（int）操作是O（N），而size（）操作是O（1）复杂度。
我可能有点迟到回答，但我认为这个for循环实际上是 
说明
每次循环迭代，您将访问列表的第i个索引。 因此，您的通话顺序为：
这是因为每次迭代i都会递增，并且您循环n次。
因此，可以使用以下总和来评估方法调用的总数：
简答：这取决于对问题的解释。
如果问题是如果我想要找到第100个位置（比如调用.get(100) ）那么我将要跳多少次，因为我需要经历整个列表一次，因此复杂性将是O（N） 。
如果问题是要求通过检查每个索引（如.get(1) .get(2) ，…，。 .get(100) ）来查找第i个变量的复杂性，那么复杂度将为O（N²）正如迈克尔所解释的那样。
答案很长：
计算大小的复杂性取决于您的实现。 如果遍历整个列表以找到大小，则大小计算的复杂度为O（N） （第一种情况为O（2N） ，第二种情况为O（N²+ N） ）< - 最后一部分也是取决于你的实现，因为我认为你正在计算for循环的大小。
如果您将大小保存为每次添加元素时变大的实例变量，则第一和第二种情况下的大小和复杂度都会为O（1） 。
我们将O（2N） （或任何O（aN + b）的情况 ）转换为O（N）的原因是因为我们只关心处理数据所花费的时间的增长。 如果N很小，代码将无论如何都会快速运行。 如果N很大，代码可能会在很长的时间内运行，具体取决于复杂性，但与更复杂的实现相比，常量a和b不会产生太大影响。
假设代码在2秒内运行，以获得O（N）复杂度的小输入N.
随着值变大：N，2N，3N，4N，…，kN
如果代码具有复杂度O（N），则时间将是：2,4,6,8，…，2k
如果代码具有复杂度O（2N），则时间将是：4,8,12,16，…，2k * 2
如果代码的复杂度为O（N²），则时间为： 4,16,36,64 ，…，（2k）²
正如您所看到的，最后一个实现失控非常快，而第二个实现只比简单线性慢两倍。 因此O（2N）较慢，但与O（N²）解决方案相比几乎没有。