runtime - append 过程的运行时是否为O(n)？

Question

例如，在OCaml中，当您将项目追加到长度为n的列表中时。

x@[mylist]

Answer 1

是的，OCaml中@的运行时是O(n)(其中n是左操作数的长度)。

通常，将O(n) append 到不可变的单链表(或与此相关的不可变的双链表)的末尾。