algorithm - List.mem 的复杂性

Question

我有一个处理列表的算法，我想表达它的复杂性。

在算法中，我有List.mem a l一个循环，我不确定如何考虑 的复杂性List.mem，它必须是O(List.length(l))，还是Ocaml可以在里面做一些魔术来比O(List.length(l))？

Answer 1

没有魔法，这是实现（OCaml 3.12.0）：

let rec mem x = function
    [] -> false
  | a::l -> compare a x = 0 || mem x l

如果您有 OCaml 源代码分发，则它位于名为stdlib/list.ml（第 135 行）的文件中。

Answer 2

不，对于链表，理论上检查成员资格的最佳方法是 O(n)。您可以通过牺牲空间来改进这一点，即使用哈希表代替，或者如果您关心顺序，则在此列表旁边有一个哈希表。