List.mem의 복잡성

Question

나는리스트를 조작하는 알고리즘을 가지고 있으며, 나는 그 복잡성을 표현하고자한다. 알고리즘에서

, 내가 루프 내부 List.mem a l을 가지고, 내가 List.mem의 복잡성을 고려하는 방법을 잘 모르겠습니다, 그것은 O(List.length(l))이거나 Ocaml는 O(List.length(l))보다 더 나은 것으로 내부의 마법 뭔가를 할 수 있습니까?

Answer 1

, 여기에 구현 (OCaml의의 3.12.0)이다.

Answer 2

아니요, 연결된 목록에서 이론적으로 회원 확인을 위해 할 수있는 최선은 O (n)입니다. 공간을 희생 시키면 해시 테이블 대신 해시 테이블을 사용하거나 주문과 관련하여이 목록과 함께 해시 테이블을 만들면됩니다. 당신은 OCaml의 소스 배포판이있는 경우

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

, 이것은 stdlib/list.ml (라인 135)라는 이름의 파일에 : 마법은 없다