2

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

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

4

2 回答 2

5

没有魔法,这是实现(OCaml 3.12.0):

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

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

于 2012-06-06T01:56:28.467 回答
1

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

于 2012-06-06T01:56:16.610 回答