ocaml - OCaml 中两个列表之间比较的复杂性是什么？

Question

如果 l1 和 l2 是两个列表，l1 = l2 的成本是 O(N) 还是 O(1)？

进一步的问题:

如果l1=l2，l1和l2会共享同一个物理内存吗？

字符串呢？ s1 = s2 会花费 O(1) 吗？

Answer 1

对于结构比较 = 您至少需要查看所有数据，因此在最坏的情况下(相等值)，对于列表和字符串，它(几乎，请参见下面的评论)总是 O(n) .物理比较 == 是 O(1) 你只是比较指针。

但是请注意，在您自己的数据结构上，通过确保在值构造期间没有两个结构相同的值将使用不同的物理内存，可以将结构比较实现为物理比较。这称为散列分析，您可以在 this 中找到更详尽的解释。论文(doi)。

一般来说，对于列表，您不能从 l1 = l2 推断出它们共享相同的物理内存，因为这取决于它们的构造方式，因为 OCaml 没有散列列表。这也适用于字符串。