使用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）操作，因为您必须html" target="_blank">遍历整个列表。
此外，您错误地计算了.get（）的时间复杂度。对于big-O，最重要的是 最坏情况的
计算。对于链接列表，检索的最坏情况是元素位于列表的末尾，因此也是O（N）。
总而言之，您的算法每次迭代将花费O（2N）= O（N）时间。我希望您可以从那里找出整个循环的时间复杂度。
顺便说一句，在现实世界中，您可能只想在循环之前计算一次大小，这恰恰是因为它可能效率很低。显然，如果列表的大小可以在循环期间更改，则这不是一个选择，但是这种非变异算法看起来并非如此。
-
我想知道下面代码的时间复杂度是O（n^3）还是O（n^2）
-
我得到O（n log(n))作为答案。这是计算这种类型列表的搜索方法的正确方法吗？
-
问题内容： 我遇到了非常奇怪的Java行为，但我不知道这是一个bug，还是我错过了一些东西。 该代码只需遍历stateStack（LinkedList）列表并销毁所有状态。 引发了以下异常： 该代码通常可以正常工作，并且已经投入生产一年多了。 这可能是Java错误吗？ / 更新 / destroy（）调用不会修改stateStack。如果可以的话，我猜Java会抛出ConcurrentModifi
-
以下代码的时间复杂度是多少？ 在嵌套循环中，如果外循环1需要O（1）时间，内循环2需要O（logn）时间，内循环3需要O（n）。那么总的tc是O（1）O（logn）O（n）=O（nlogn）。这是真的吗？ 请解释一下。
-
我想确定两个函数的复杂性。 第一个我只需要知道我的解决方案是否正确，第二个是因为我正在努力寻找解决方案的两个递归调用，如果可能的话，最好进行工作，这样我就可以了解它是如何完成的。 第一： 尝试的解决方案： 第二： 任何帮助将不胜感激。 当做
-
我对确定上述代码的BigO有点困惑。如果在最外层的循环中，则为（int x=1；x 然而，考虑到最外层循环迭代n 2次，这会改变bigO还是加法常数无关紧要的规则？最后，如果最内层循环迭代n 2次而不是n，会改变什么吗？ 非常感谢。