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行)的文件中.