Понимание утечки пространства с помощью стрелки

Question

Я испытываю затруднения в понимании утечки пространства в статье Худака «Заткнуть пробел в космосе» https://www.sciencedirect.com/science/article/pii/S1571066107005919.

1) Что именно означает O (n) сложность пространства?Общий объем памяти, выделенный относительно размера ввода?Как насчет сбора мусора по пути?

2) Если выполняется определение в 1), как получается, что на странице 34 они говорят, что если dt является константой, тип сигнала похож на тип списка и запускается впостоянное пространство?Не создает ли IntegraC еще 1 единицу пространства на каждом шаге, то есть n единиц, то есть все еще O (n)?

3) Я совершенно не понимаю, почему сложность времени равна O (n ^ 2),У меня есть предположения о том, что нужно оценивать (i ', i' ', i' '' на рисунке ниже), но как это O (n ^ 2)?

Изображение представляет шаги оценки, которые я нарисовал в лямбда-графе.Каждый шаг видит свою структуру ДОБАВЛЕННОЙ в общий объем, а не ЗАМЕНЯЯ что-либо в нем.Квадрат обозначает указатель, поэтому квадрат (i ') на шаге 2 обозначает блок i' на шаге 1, например.

Answer 1

Я только кратко взглянул на газету, но постараюсь.

1. Как обычно, сложность пространства означает, что в какой-то момент времени нам нужно одновременно хранить столько «вещей» в памяти. GC говорит, что мы можем восстановить память из переменных, в которых мы больше не нуждаемся, но здесь мы должны помнить вещи O(n), память еще не может быть восстановлена, потому что нам (возможно) все еще нужен доступ к любой ее части. Вы можете думать об этом как о том, что повторное использование памяти (например, с помощью GC) увеличивает время, но не увеличивает сложность пространства. Здесь n вычисляет n-е значение, предоставляя n временных шагов (dts).

2. Если dt является константой, то вместо типа C a = (a, dt -> C a) мы имеем C' a = (a, C' a), который является просто (непустым) списком. Суть статьи в том, что любой тип можно заставить работать в постоянном пространстве, но если он изоморфен спискам, то это решаемая проблема. Чтобы понять, почему создание нового значения на каждом шаге может быть постоянной памятью, рассмотрим возможную оценку (iterate f)!!n, где мы храним только x, затем перезаписываем его с f (x), затем перезаписываем его с f (f (x)) и так далее до у нас есть f^n(x), но мы всегда используем эту одну ячейку памяти для наших значений (и технически вторую ячейку для итерации до n).

3. Давайте рассмотрим действительно простой пример оценки с учетом этих различных сложностей. Допустим, мы генерируем список из некоторого начального числа, где каждый элемент является суммой всех предыдущих элементов. Чтобы вычислить каждый следующий элемент, мы могли бы хранить всю начальную часть p списка в памяти (O(Len(p))) и суммировать ее (O(Len(p))), в результате чего общая память O(n) и время выполнения O(n^2) to retrieve the n` Этот элемент - или мы могли бы заметить, что это фактически то же самое, что удвоение предыдущего элемента, что позволяет нам использовать постоянную память и линейное время. Я думаю, что приведенный раздел аналогии весьма полезен - можете ли вы механически выписать преемников для первых нескольких значений и увидеть, как две разные стратегии оценки быстро расходятся в необходимых шагах?