Czy czas wykonywania procedury dołączania O (n)?

Question

Na przykład w OCaml, gdy dodajesz element do listy o długości n.

x@[mylist] 

Answer 1

Tak, runtime @ w SML jest O(n) (gdzie n jest długość lewego argumentu).

Generalnie dołączanie do końca niezmiennej, pojedynczo połączonej listy (lub niezmiennej podwójnie połączonej listy) zawsze będzie O(n).

Answer 2

Podsumowując, tak.

Aby to zilustrować, prostą funkcją (nie ogon rekurencyjne) dodać można zapisać w następujący sposób:

let rec (@) xs ys = 
    match xs with 
    | [] -> ys 
    | x::xs' -> x::(xs' @ ys) 

więc wewnętrznie dodać (@) rozkłada się pierwszą listę (xs) i używa cons (::) operator, aby utworzyć listę wynikową. Łatwo zauważyć, że istnieje n kroków poprzedzających (::), gdzie n jest długością pierwszej listy.

Answer 3

Tak, jak wspomniano, istnieją dwa powody, dlaczego to musi być O (n):

1. musi iteracyjne do końca pojedynczo-połączonej listy, która zajmuje O (n)

2. że pary są niezmienne, należy skopiować wszystkie pary w pierwszej listy, aby dodać, który również trwa o (n)

Podobnym interesujący temat tail-rekurencyjne vs nie ogona rekursywnego wa ys, aby dołączyć

Answer 4

Fragment kodu nie pasuje do pytania, co sugeruje, że nie masz pewności co do tego, co robi operator lub z którego operatora korzystać.

Operator @ lub List.append łączy 2 listy, a list1 @ list2 przyjmuje czas O (długość (lista1)) i nie jest rekursywny. rev_append jest rekursywny, ale wciąż O (n) w czasie. Najczęstszym sposobem dodania elementu do listy jest jednak konstruktor ::, a item :: mylist zajmuje O (1) czas.