Превратить программу с квадратичным временем в линейную с помощью моноида?

Question

Когда я читал статью, посвященную лемме Йонеды и ее связи с оптикой профессора, я натолкнулся на следующее утверждение:

... Теорема Кэли для моноидов (это уловка, которая позволяетиспользование параметра накопления, который часто может превратить программу с квадратичным временем в программу с линейным временем) ...

Интересующая меня часть - the trick ... quadratic-time... into a linear-time one.Как это работает?

PS Я знаком с моноидами и общими математическими обозначениями для них, поэтому не стесняйтесь использовать их, если необходимо, или придерживайтесь Haskell.

Answer 1

После оригинальной статьи Х. Берда, ведущим примером этого утверждения является обращение списка для односвязных списков, которое можно определить как

reverse([a : x]) = append(reverse x, a)

В прямой реализации добавить a до конца хвоста x требует n-1 операций поиска, чтобы найти конец, и количество операций для reverse x, так что общее усилие составляет (n-1)+...+2+1=n*(n-1)/2.

В линейной реализации используетсяасимметричная сложность операции append при append(x,y) имеет стоимость, пропорциональную длине x, тогда как длина y не играет никакой роли.В качестве частичной операции append является эндоморфизмом в пространстве списков, append(x) y = append(x,y).Теперь представьте перевернутый список как результат объединения этих эндоморфизмов

reverse([a1,a2,...,an])=append(an) ... append(a2) append(a1) []

, из которых восстановление списка является операцией с линейными затратами.Ранее квадратичная «основная» стоимость «скрыта» в управлении стеком операций.Однако, в конце концов, это на самом деле не нужно, так как восстановление результирующего списка может начаться с извлечения первого элемента.Для этого нужен «накопительный элемент» в том же диком псевдокоде

reverse(x) = reverse_recursion(x,[])

, где

reverse_recursion([a : x], y) = reverse_recursion(x, [a : y])

с

reverse_recursion([], y) = y