追加程序O（n）的运行时间是？

Question

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

x@[mylist] 

Answer 1

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

通常追加到一个不可变的单向链表（或不可变的双向链表）的末尾将始终为O(n)。

Answer 2

总之，是的。

为了说明，一个简单的（不是尾递归）附加功能可以写成如下：

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

所以内部追加（@）打破了第一个列表（xs），并使用cons（::）运算符来构建结果列表。很容易看到有n个预先步骤（::），其中n是第一个列表的长度。

Answer 3

是，如前所述，有两个原因，它必须是O（N）：

1. 你必须重复的单链表的末尾，这需要为O（n）

2. 由于对是不可变的，你必须将所有对在第一个列表，以追加，这也需要为O（n）

一个相关的有趣的话题是尾递归与非尾递归WA ys追加

Answer 4

您的代码片段与您的问题不符，这表明您对操作员的操作或要使用的操作员感到困惑。

@或List.append运算符连接2个列表，并且list1 @ list2以O（长度（列表1））时间并且不是尾递归。 rev_append是尾递归的，但仍然是O（n）。然而，将项目添加到列表的通常方法是使用::构造函数，而item :: mylist需要O（1）次。