6
Ad esempio, in OCaml quando si aggiunge un elemento a un elenco di lunghezza n.Il runtime della procedura di aggiunta O (n)?
[email protected][mylist]
A
risposta
7
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).
1
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.
3
Sì, come detto, ci sono due ragioni per cui essa deve essere O (n):
Devi itera fino alla fine della lista semplicemente legata, che prende O (n)
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
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).
che dipende da come viene eseguita l'append. Se è una struttura lineare e si aggiunge alla fine, allora sì. Se si tratta di un'appendice alla testa di una struttura lineare, allora è O (1), ma poi si ha il sovraccarico di spostare i nodi N-1. Se l'elenco è collegato e l'elenco contiene riferimenti a capo e coda, allora è O (1). – mslot