Блог

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

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

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

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

Изображение представляет этапы оценки, которые я нарисовал в лямбда-графической нотации. На каждом шаге его структура ДОБАВЛЯЕТСЯ к общей области, а не ЗАМЕНЯЕТ все, что в ней есть. Квадрат обозначает указатель, поэтому квадрат (i ‘) на шаге 2 обозначает блок i’ на шаге 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-го элемента — или мы могли бы заметить, что это фактически то же самое, что удвоение предыдущего элемента, что позволяет нам использовать постоянную память и линейное время. Я думаю, что приведенный раздел аналогии весьма полезен — можете ли вы механически выписать преемников для первых нескольких значений и посмотреть, как две разные стратегии оценки быстро расходятся в необходимых шагах?