java - Java 中的大 O 表示法

Question

嘿伙计们，有人可以为我解释一下大 o 符号吗？

Answer 1

由于您有一个数组，这意味着连续的内存。这意味着对任何给定索引的查找将在一个操作中进行，因为不需要像在链表中那样迭代。所以它是 O(1)。

在没有排序或排序的情况下比较两个 ArrayList 对象 A 和 B 是 O(n^2)，因为 ArrayList A 中的每个元素都必须与 B 中的每个元素进行比较。所以 A 中有 n 个元素，B 中有 n 个元素。那将导致 A 中的每个元素都需要与 B 进行 n 次比较。由于 A 中有 n 个元素，即 n 次比较，O(n^2)。

尽管如果您使用排序算法，它将与排序算法一样快，例如 O(n log n) 时间或 O(n)，具体取决于所使用的排序算法。

在未排序的数组中搜索特定的目标值确实是 O(n)。之所以如此，是因为您必须搜索数组中的每个元素以检查它是否存在。由于列表中有 n 个元素，这意味着有 n 个比较。

Answer 2

1- 因为数组元素可以随机访问（不需要像链表一样从一个单元格移动到另一个单元格）所以你基本上可以说 array[28] 这是 O(1)

2-比较两个数组列表可以以一种会导致较低的大O但排序的方式完成。

您可以使用合并排序或快速排序 O(nlg(n)) 对每个数组列表进行排序，然后在 O(n) 中比较两个排序列表。结果是 O(nlgn)。

但是另一种算法（没有排序）将遍历一个数组（n）中的每个元素。然后检查该元素是否是另一个数组（n）（并将其标记为正确处理重复项）。后一种算法是 O(n^2)。

3- 是的。您必须一一浏览整个列表，直到找到所需的元素。