Списки рекурсивны и состоят из головы и хвоста, который список.
Операция "конкатенации", должна быть n сложности,
и генераторы списков тоже добавляют свое n.
детерминированность (определенность). Предполагает получение однозначного результата вычислительного процecca при заданных исходных данных. Благодаря этому свойству процесс выполнения алгоритма носит механический характер;
На каждом рекурсивном вызове Эрланга, список разделяется на два других, меньших, а входной после выхода из функции пропадает далее сортируються меньшие списки, так что константность памяти сохранится. А сложность n*log(n) сохраняется, так это выражение того-же самого принципа быстрой сортировки.
А алгоритм не должен обладать свойством «повторяемости», а от выбора этого пивота будем получать разные «неповторимые» реализации сложности, когда же кончается алгоритм?
А мне остается поинтересоваться, а как же «понятный» алгоритм быстрой сортировки сейчас вот записать, восстановить из памяти…
Понятность и вычислительная сложность конечно разные понятия, но когда они приближаются, тогда решение «хорошее».
Последовал совету, вот приведу решение, которое в комментариях приводят:
import heapq
class Solution:
def trapRainWater(self, heightMap):
"""
:type heightMap: List[List[int]]
:rtype: int
"""
rows = len(heightMap)
if rows < 3:
return 0
cols = len(heightMap[0])
if cols < 3:
return 0
heap = []
for i in range(rows):
for j in (0, cols-1):
heap.append((heightMap[i][j], i, j))
heightMap[i][j] = None
for j in range(1, cols-1):
for i in (0, rows-1):
heap.append((heightMap[i][j], i, j))
heightMap[i][j] = None
heapq.heapify(heap)
water = 0
while heap: # iterate while heap has elements
max_height, i, j = heapq.heappop(heap)
for x, y in [(i, j + 1), (i + 1, j), (i, j - 1), (i - 1, j)]:
if (0 <= x < rows) and (0 <= y < cols):
height = heightMap[x][y]
if height is None:
continue
if height >= max_height:
heapq.heappush(heap, (height, x, y))
else:
water += max_height - height
heapq.heappush(heap, (max_height, x, y))
heightMap[x][y] = None
return water
Это формализация, да тут одни heappush()… это разве понятно?
Продолжу про быструю сортировку, по-моему «понятно», это когда можно взять и записать этот алгоритм по памяти, проведите эксперимент, запишите сюда быструю сортировку «по-памяти», реально ли ее восстановить?
А быструю сортировку в Эрланге еще раз продемонстрирую:
qsort([])->[];
qsort([H|T])->qsort([X||X<-T,X<H])++[H|qsort([X||X<-T,X>=H])].
А мне кажется, что такие программы, показывают математическую суть задачи, у каждой неизвестной осталось указать квантор *существования* или *всеобщности*, заменить ":-" на «следование» и получаем математическую модель.
И мне интересно, как же будет выглядеть императивное решение этой задачи?, не так ли будет понятно как быстрая сортировка?
Я показал два решения, первое «генерировать и проверить» не проходило все приведенные тесты, второе с использованием CLP проходит все плюс еще приведенные…
В данном случае, мне интересна «вычислительная сложность», но хочу обратить внимание на «познавательную сложность». Какая задача труднее, сформулировать решения прибегая к алгоритму или описав формулировку?
При представлении входных данных в виде списка из списков выразить понятие «путь» становиться не просто, без индексов очень громоздко.
Можно превратить этот массив в подобие графа и обрабатывать список из связей(переходов) — так реальнее, надо думать…
Вот, правильное замечание, там два генератора списка, которые сканируют весь список целиком, а если заменить это на один цикл, какая будет разница по скорости?
Списки рекурсивны и состоят из головы и хвоста, который список.
Операция "конкатенации", должна быть n сложности,
и генераторы списков тоже добавляют свое n.
Не понятно в этой записи, а что с самим пивотом происходит, он на месте остался?
Вот, а я нашел вот такое свойство алгоритмов:
На каждом рекурсивном вызове Эрланга, список разделяется на два других, меньших, а входной после выхода из функции пропадает далее сортируються меньшие списки, так что константность памяти сохранится. А сложность n*log(n) сохраняется, так это выражение того-же самого принципа быстрой сортировки.
Тут надо бы поподробнее, не все еще понятно.
А записать в программу его будет тоже не просто..
Это же, как ассемблер заменили на фортран, что-то стало более понятнее.
И "Эти две метрики", если это метрики, то они имеют числовое выражение.
Понятность и вычислительная сложность конечно разные понятия, но когда они приближаются, тогда решение «хорошее».
Это формализация, да тут одни heappush()… это разве понятно?
А быструю сортировку в Эрланге еще раз продемонстрирую:
qsort([])->[];
qsort([H|T])->qsort([X||X<-T,X<H])++[H|qsort([X||X<-T,X>=H])].
И мне интересно, как же будет выглядеть императивное решение этой задачи?, не так ли будет понятно как быстрая сортировка?
Спасибо, у вас замечания всегда очень критические, всех ответов не имею.
А как будете доказывать:
Предоставьте алгоритм, покажите его сложность, давайте сравнивать решения...
Кто предоставит алгоритм для сравнения?
В данном случае, мне интересна «вычислительная сложность», но хочу обратить внимание на «познавательную сложность». Какая задача труднее, сформулировать решения прибегая к алгоритму или описав формулировку?
Можно превратить этот массив в подобие графа и обрабатывать список из связей(переходов) — так реальнее, надо думать…
Вы правы, тесты беру с сайта, следующий был 50*50 и его решение не оканчивается.
Был бы рад увидеть более совершенное и лаконичное решение...
А вот так, работает еще быстрее: