¿El tiempo de ejecución del procedimiento de adición O (n) es?

Question

Por ejemplo, en OCaml cuando agrega un elemento a una lista de longitud n.

x@[mylist] 

Answer 1

Sí, el tiempo de ejecución de @ en OCaml es O(n) (donde n es la longitud del operando de la izquierda).

Por lo general, al final de una lista inmutable individualmente vinculada (o una lista doble enlace inmóvil para el caso) siempre será O(n).

Answer 2

En resumen, sí.

Para ilustrar, una simple función (no recursiva de cola) anexar podría escribirse de la siguiente manera:

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

anexar tanto internamente (@) se rompe la primera lista (xs) y utiliza cons (::) operador para construir la lista resultante. Es fácil ver que hay n pasos de anteponer (::), donde n es la longitud de la primera lista.

Answer 3

Si, como se ha mencionado, hay dos razones por las que debe ser O (n):

1. Debe iterar hasta el final de la lista simplemente enlazada, que toma O (n)

2. Desde pares son inmutables, debe copiar todos los pares en la primera lista con el fin de añadir, que también toma O (n)

Un tema interesante relacionado es recursiva de cola vs recursiva no la cola Washington ys para anexar

Answer 4

Su fragmento de código no coincide con su pregunta, lo que sugiere que está confundido sobre qué hace el operador o qué operador usar.

El operador @ o List.append concatena 2 listas, y list1 @ list2 toma el tiempo O (length (list1)) y no es recursivo de cola. rev_append es cola recursivo pero todavía O (n) en el tiempo. Sin embargo, la forma habitual de agregar un elemento a una lista es con el constructor ::, y item :: mylist toma O (1) vez.