Il runtime della procedura di aggiunta O (n)?

Question

Ad esempio, in OCaml quando si aggiunge un elemento a un elenco di lunghezza n.

x@[mylist] 

Answer 1

Sì, il tempo di esecuzione @ in OCaml è O(n) (dove n è la lunghezza del operando a sinistra).

In genere, l'aggiunta alla fine di una lista concatenata e non modificabile (o di una lista di collegamenti doppiamente immutabili) sarà sempre O(n).

Answer 2

In sintesi, sì.

Per illustrare, una semplice funzione (non ricorsiva in coda) accodare potrebbe essere scritto come segue:

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

Così internamente append (@) rompe la prima lista (xs) e utilizza cons (::) operatore per costruire la lista risultante. È facile vedere che ci sono n passi di prepending (::), dove n è la lunghezza del primo elenco.

Answer 3

Sì, come detto, ci sono due ragioni per cui essa deve essere O (n):

1. Devi itera fino alla fine della lista semplicemente legata, che prende O (n)

2. Dal coppie sono immutabili, è necessario copiare tutte le coppie nel primo elenco, al fine di aggiungere, che tiene anche O (n)

Un argomento interessante relativo è tail-ricorsiva vs ricorsiva non-coda wa ys to append

Answer 4

Lo snippet di codice non corrisponde alla tua domanda, il che suggerisce che sei confuso su ciò che l'operatore fa o quale operatore utilizzare.

L'operatore @ o List.append concatena 2 elenchi e list1 @ list2 richiede O (lunghezza (elenco1)) e non è ricorsivo in coda. rev_append è ricorsivo in coda ma sempre O (n) nel tempo. Il solito modo di aggiungere un elemento a un elenco è tuttavia con il costruttore :: e item :: mylist richiede O (1).