Временная сложность :: и @ (Ocaml)

Question

Я читал this и было интересно, если :: всегда более эффективно, чем @ или если только в этой конкретной реализации rev

let rec rev = function 
    | [] -> [] 
    | h::t -> rev t @ [h] 

let rev l = 
    let aux accu = function 
    | [] -> accu 
    | h::t -> aux (h :: accu) t 

Например, если я хотел добавить элемент в очереди, будет ли разница в этих двух методов:

let append x q = q @ [x] 

и

type 'a queue = {front:'a list; back:'a list} 
    let norm = function 
    | {front=[]; back} -> {front=List.rev back; back=[]} 
    | q -> q 

    let append x q = norm {q with back=x::q.back} 

Answer 1

@ is O(n) в размере его левого операнда. :: - O(1) и List.rev (как определено в стандартной библиотеке) - O(n).

Так что если вы примените @n раз, вы получите алгоритм O(n^2). Но если вы примените :: n раз, это всего лишь O(n), и если вы затем измените результат один раз в конце, то все равно O(n). Это верно в целом, и по этой причине любой алгоритм, который добавляется к концу списка несколько раз, должен вместо этого добавлять к началу списка несколько раз, а затем изменять результат.

Однако ваш пример отличается. Здесь вы заменяете одно единственное использование @ одним возможным использованием rev. Поскольку оба значения: O(n), вы оказываетесь в том же сложном случае, если используете rev.

Однако в случае, когда вы используете rev не будет много, так что сложность enqueuing n должны в конечном итоге амортизированной O (N) (и если вы ничего не между из очереди, это просто O (п)). Если ваша версия с использованием @ приведет к O(n^2).

Answer 2

Я читал это и было интересно, если :: всегда более эффективен, чем @

В принципе да, но вопрос достаточно размыто, чтобы найти особые случаи, когда оба являются столь же эффективными.

эффективности или сложность из операции, как правило, выражаются с помощью асимптотического эквивалента вычислительной стоимости этой операции с точкой зрения размера его входных данных. Тем не менее, мы можем сравнить именно сложность :: и @, заявив:

1. Сложность вычислений x :: lst является O (1), то есть, она ограничена постоянной стоимости независим входов.

2. Сложность вычислений a @ b is O (List.length a).

(нотация используется, называется большой-O обозначения или Ландау обозначения и должны быть описаны в большинстве компьютерных наук учебников.)

Например, если я хотел бы добавить элемент в очереди, будет ли разница в этих двух методах:

Эти два метода имеют эквивалентную сложность, работает в O (длина q). Сложность второй операции переносится операцией List.rev.