5

我有一个实用的方法来确定使用 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()，这涉及到查找（以确定链表中有多少节点）。

在计算这段代码的复杂度时，是否应该考虑到这一点？或者计算大小不算作查找？

4

4 回答 4

8

我可能回答得有点晚了，但我认为这个 for 循环实际上是O(n^2)

解释

您将访问列表的第 i 个索引的每次循环迭代。因此，您的呼叫顺序将是：

顺序

这是因为每次迭代i都会递增，并且您正在循环n次。

因此，可以使用以下总和来评估方法调用的总数：

在此处输入图像描述

于 2016-12-10T00:10:31.353 回答
4

在 Java LinkedList 中，get(int) 操作是 O(N)，size() 操作是 O(1) 复杂度。

于 2015-12-20T00:21:16.653 回答
2

由于它是一个链表，因此确定大小将是一个 O(N) 操作，因为您必须遍历整个列表。

此外，您错误地计算了 .get() 的时间复杂度。对于 big-O，重要的是最坏情况的计算。对于链表，最坏的检索情况是元素在链表的末尾，所以也是 O(N)。

总而言之，您的算法每次迭代将花费 O(2N) = O(N) 时间。我希望你能从那里弄清楚整个循环的时间复杂度是多少。

顺便说一句，在现实世界中，您可能只想在循环之前计算一次大小，正是因为这样可能效率低下。显然，如果列表的大小可以在循环期间发生变化，这不是一个选项，但对于这种非变异算法来说，情况似乎并非如此。

于 2013-03-04T00:15:52.780 回答
2

简短回答：这取决于对问题的解释。

如果问题是问如果我想找到第 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²) 解决方案相比几乎没有什么。

于 2017-08-17T03:08:41.720 回答