我有一个实用的方法来确定使用 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()，这涉及到查找（以确定链表中有多少节点）。
在计算这段代码的复杂度时，是否应该考虑到这一点？或者计算大小不算作查找？
我可能回答得有点晚了，但我认为这个 for 循环实际上是
解释
您将访问列表的第 i 个索引的每次循环迭代。因此，您的呼叫顺序将是：
这是因为每次迭代i都会递增，并且您正在循环n次。
因此，可以使用以下总和来评估方法调用的总数：
在 Java LinkedList 中，get(int) 操作是 O(N)，size() 操作是 O(1) 复杂度。
由于它是一个链表，因此确定大小将是一个 O(N) 操作，因为您必须遍历整个列表。
此外，您错误地计算了 .get() 的时间复杂度。对于 big-O，重要的是最坏情况的计算。对于链表，最坏的检索情况是元素在链表的末尾，所以也是 O(N)。
总而言之，您的算法每次迭代将花费 O(2N) = O(N) 时间。我希望你能从那里弄清楚整个循环的时间复杂度是多少。
顺便说一句，在现实世界中，您可能只想在循环之前计算一次大小，正是因为这样可能效率低下。显然，如果列表的大小可以在循环期间发生变化，这不是一个选项，但对于这种非变异算法来说，情况似乎并非如此。
如果问题是问如果我想找到第 100 个位置（比如调用），我必须跳多少次列表.get(100)，那么复杂性将是O(N)，因为我需要遍历整个列表一次。
.get(1)如果问题是通过检查每个索引（如, .get(2), ..., ）来询问找到第 i 个变量.get(100)的复杂性，那么复杂性将是O(N²)，正如 michael 所解释的那样。
计算大小的复杂性取决于您的实现。如果您遍历整个列表以查找大小，则大小计算的复杂度将为O(N) （在第一种情况下为O(2N) ，在第二种情况下为O(N² + N)）<-这最后一部分也是取决于您的实现，因为我认为您正在计算 for 循环之外的大小。
如果您将大小保存为每次添加元素时都会变大的实例变量，那么您将拥有O(1)的大小，并且对于第一种和第二种情况具有相同的复杂性。
我们将O(2N)（或O(aN + b)的任何情况）舍入到O(N)的原因是因为我们只关心处理数据所花费的时间的增长。如果 N 很小，代码无论如何都会运行得很快。如果 N 很大，则代码可能会运行更多时间，具体取决于复杂性，但与更糟糕的复杂性实现相比，常量 a 和 b 不会有太大影响。
假设对于 O(N) 复杂度的小输入 N，代码在 2 秒内运行。
随着值变大：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²) 解决方案相比几乎没有什么。