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

stdlib/list.mlOCamlソースディストリビューションがある場合、これは（135行目）という名前のファイルにあります。

Answer 2

いいえ、リンクリストを使用すると、メンバーシップを確認するために理論的に実行できる最善の方法はO（n）です。スペースを犠牲にすることで、つまり、代わりにハッシュテーブルを使用するか、順序が気になる場合はこのリストの横にハッシュテーブルを配置することで、これを改善できます。