Время выполнения процедуры добавления O (n)?

Question

Например, в OCaml, когда вы добавляете элемент в список длиной n.

x@[mylist]

Answer 1

Да, время выполнения @ в OCaml равно O(n) (где n - длина левого операнда).

Обычно добавляется в конец неизменяемого односвязного списка (илинеизменный двусвязный список) всегда будет O(n).

Answer 2

Ваш фрагмент кода не соответствует вашему вопросу, что говорит о том, что вы не понимаете, что делает оператор или какой оператор использовать.

@ или List.append оператор объединяет 2 списка, а list1 @ list2 занимает время O (length (list1)) и не является хвостовой рекурсивной.rev_append хвост рекурсивен, но все еще O (n) во времени.Обычный способ добавить элемент в список, однако, с помощью конструктора ::, а item :: mylist занимает O (1) время.

Answer 3

Да, как уже упоминалось, есть две причины, почему это должно быть O (n):

1. Вы должны выполнить итерацию до конца односвязного списка, который принимает On)

2. Поскольку пары являются неизменяемыми, для добавления необходимо скопировать все пары в первом списке, что также занимает O (n)

Связанная интересная тема - хвостовые рекурсивные и не хвостовые рекурсивные способы добавления

Answer 4

В целом, да.

Для иллюстрации, простая (не хвостовая рекурсивная) функция добавления может быть записана следующим образом:

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

Внутреннее добавление (@)разбивает первый список (xs) и использует оператор cons (::) для построения результирующего списка.Легко видеть, что есть n шагов добавления (::), где n - длина первого списка.