Особенности применения append - История изменений

SergeMukhin в 07:20, 6 ноября 2007

2007-11-06T07:20:34Z

Victor Yukhtenko в 13:18, 1 ноября 2007

2007-11-01T13:18:47Z

← Предыдущая		Версия 15:18, 1 ноября 2007
Строка 48:		Строка 48:
	Т.е. присоединяет пустой список к элементам дерева.		Т.е. присоединяет пустой список к элементам дерева.
	[[Категория:VipLanguage]]		[[Категория:VipLanguage]]
	[[Категория:~~Комментарии~~]]		[[Категория:VipКомментарии]]

Victor Yukhtenko в 19:03, 25 октября 2007

2007-10-25T19:03:20Z

← Предыдущая		Версия 21:03, 25 октября 2007
Строка 47:		Строка 47:
	</vip>		</vip>
	Т.е. присоединяет пустой список к элементам дерева.		Т.е. присоединяет пустой список к элементам дерева.
			[[Категория:VipLanguage]]
	[[Категория:Комментарии]]		[[Категория:Комментарии]]

Victor Yukhtenko в 19:28, 21 сентября 2007

2007-09-21T19:28:50Z

← Предыдущая		Версия 21:28, 21 сентября 2007
Строка 20:		Строка 20:
	LeftElems = elems(Left),		LeftElems = elems(Left),
	RightElems = elems(Right),		RightElems = elems(Right),
	Elems = ~~'''~~append~~'''~~(LeftElems, [Node\|RightElems]).		Elems = append(LeftElems, [Node\|RightElems]).
	</vip>		</vip>
	Т.е. мы находим элементы в левом поддереве, затем в правом поддереве и соединяем их, вставив узел перед элементами правого поддерева.		Т.е. мы находим элементы в левом поддереве, затем в правом поддереве и соединяем их, вставив узел перед элементами правого поддерева.

Victor Yukhtenko в 19:28, 21 сентября 2007

2007-09-21T19:28:03Z

← Предыдущая		Версия 21:28, 21 сентября 2007
Строка 1:		Строка 1:
	автор: Thomas Linder Puls. PDC		'''автор: Thomas Linder Puls. PDC'''

	Соединение списков в Прологе затратно по своей природе. Эта проблема связана с «персистентной» природой прологовских списков. Структура персистентных данных неизменяема и неуничтожима при манипулировании этими данными.		Соединение списков в Прологе затратно по своей природе. Эта проблема связана с «персистентной» природой прологовских списков. Структура персистентных данных неизменяема и неуничтожима при манипулировании этими данными.
Строка 5:		Строка 5:
	Например, если я соединяю два списка, то в результате они продолжают существовать. Способ создания объединенного списка без разрушения исходных списков, состоит в копировании первого списка в начало второго. Так, соединяя L1 и L2, мы повторно используем L2 в качестве хвоста нового списка, а L1 копируется в начало нового списка. Сами элементы не копируются, копируются только ячейки списка. Поэтому затраты на соединение пропорциональны длине первого списка.		Например, если я соединяю два списка, то в результате они продолжают существовать. Способ создания объединенного списка без разрушения исходных списков, состоит в копировании первого списка в начало второго. Так, соединяя L1 и L2, мы повторно используем L2 в качестве хвоста нового списка, а L1 копируется в начало нового списка. Сами элементы не копируются, копируются только ячейки списка. Поэтому затраты на соединение пропорциональны длине первого списка.

	Используя предикат append нужно быть очень осторожным, очень легко изменить линейную сложность алгоритма (О(N)) на квадратичную (О(N*N)).		Используя предикат '''append''' нужно быть очень осторожным, очень легко изменить линейную сложность алгоритма (О(N)) на квадратичную (О(N*N)).
	Рассмотрим пример. Имеем бинарное дерево:		Рассмотрим пример. Имеем бинарное дерево:
	<vip>		<vip>
Строка 13:		Строка 13:
	tree(binTree Left, integer Node, binTree Right).		tree(binTree Left, integer Node, binTree Right).
	</vip>		</vip>
	Мы хотим создать список всех элементов дерева. Вот очевидный способ решения этой задачи, используя предикат append:		Мы хотим создать список всех элементов дерева. Вот очевидный способ решения этой задачи, используя предикат '''append''':
	<vip>		<vip>
	clauses		clauses
Строка 20:		Строка 20:
	LeftElems = elems(Left),		LeftElems = elems(Left),
	RightElems = elems(Right),		RightElems = elems(Right),
	Elems = append(LeftElems, [Node\|RightElems]).		Elems = '''append'''(LeftElems, [Node\|RightElems]).
	</vip>		</vip>
	Т.е. мы находим элементы в левом поддереве, затем в правом поддереве и соединяем их, вставив узел перед элементами правого поддерева.		Т.е. мы находим элементы в левом поддереве, затем в правом поддереве и соединяем их, вставив узел перед элементами правого поддерева.
Строка 26:		Строка 26:
	Это совершенно очевидный алгоритм, но очень плохой. Проблемой является левое поддерево: сначала мы создаем список всех его элементов, затем соединяем, копируя этот список перед оставшимися элементами. В наихудшем случае все дерево представляет со-бой простой путь вниз.		Это совершенно очевидный алгоритм, но очень плохой. Проблемой является левое поддерево: сначала мы создаем список всех его элементов, затем соединяем, копируя этот список перед оставшимися элементами. В наихудшем случае все дерево представляет со-бой простой путь вниз.

	Если в дереве N узлов, то мы имеем одну вершину и N-1 элемен-тов в левом поддереве и пустое правое поддерево. В этом уровне, append выполнит N-1 операцию. На следующем уровне, по аналогии, будут выполнены N-2 операций, т.д. По моим представлениям о высшей математике, всего получится N*N/2 операций. Поэтому, в наихудшем случае, этот алгоритм имеет квадратичную сложность. Правда, в лучшем случае, алгоритм линейный. Оставляю вам доказательство этого утверждения.		Если в дереве N узлов, то мы имеем одну вершину и N-1 элемен-тов в левом поддереве и пустое правое поддерево. В этом уровне, '''append''' выполнит N-1 операцию. На следующем уровне, по аналогии, будут выполнены N-2 операций, т.д. По моим представлениям о высшей математике, всего получится N*N/2 операций. Поэтому, в наихудшем случае, этот алгоритм имеет квадратичную сложность. Правда, в лучшем случае, алгоритм линейный. Оставляю вам доказательство этого утверждения.

	Лично я никогда не применяю append в рекурсивном алгоритме. Я использую его, например, для соединения содержимого двух списковых элементов управления. Вообще, я практически никогда не использую append. Когда я его вижу, это вызывает ~~насторожен~~-~~ность:~~ нет ли проблемы с этим алгоритмом?		Лично я никогда не применяю '''append''' в рекурсивном алгоритме. Я использую его, например, для соединения содержимого двух списковых элементов управления. Вообще, я практически никогда не использую '''append'''. Когда я его вижу, это вызывает настороженность - нет ли проблемы с этим алгоритмом?

	К счастью, в нашем случае легко избежать использования append. Имеется ~~стандарт-ная~~ «хитрость», которая помогает решить проблему без append с линейной сложностью в худшем случае.		К счастью, в нашем случае легко избежать использования '''append'''. Имеется стандартная «хитрость», которая помогает решить проблему без '''append''' с линейной сложностью в худшем случае.
	Введем вспомогательный предикат, который не только собирает узлы, но и ~~объеди-няет~~ их в список. Звучит это еще более сложно, чем раньше, но в действительности это не так. Вот предлагаемый предикат:		Введем вспомогательный предикат, который не только собирает узлы, но и объединяет их в список. Звучит это еще более сложно, чем раньше, но в действительности это не так. Вот предлагаемый предикат:
	<vip>		<vip>
	clauses		clauses
Строка 39:		Строка 39:
	M = elems_append(Left, [Node\|RightL]).		M = elems_append(Left, [Node\|RightL]).
	</vip>		</vip>
	Если дерево пусто, то просто возвращается исходный список. Если дерево не пусто, то сначала присоединяем элементы правого дерева к L, затем помещаем узел в начало и, наконец, присоединяем элементы левого дерева. В результате процесс идет с конца в начало. Этот алгоритм не только не использует append, но даже в худшем случае имеет сложность О(N). Оставляю вам доказательство этого.		Если дерево пусто, то просто возвращается исходный список. Если дерево не пусто, то сначала присоединяем элементы правого дерева к L, затем помещаем узел в начало и, наконец, присоединяем элементы левого дерева. В результате процесс идет с конца в начало. Этот алгоритм не только не использует '''append''', но даже в худшем случае имеет сложность О(N). Оставляю вам доказательство этого.

	Этот предикат не решает исходной проблемы, но следующий предикат делает это:		Этот предикат не решает исходной проблемы, но следующий предикат делает это:
Строка 47:		Строка 47:
	</vip>		</vip>
	Т.е. присоединяет пустой список к элементам дерева.		Т.е. присоединяет пустой список к элементам дерева.
			[[Категория:Комментарии]]

Victor Yukhtenko: «Эффективность применения append» переименована в «Особенности применения append»: Более точно

2007-09-21T19:22:38Z

«Эффективность применения append» переименована в «Особенности применения append»: Более точно

← Предыдущая	Версия 21:22, 21 сентября 2007
(нет различий)

Victor Yukhtenko в 19:15, 21 сентября 2007

2007-09-21T19:15:00Z

← Предыдущая		Версия 21:15, 21 сентября 2007
Строка 3:		Строка 3:
	Соединение списков в Прологе затратно по своей природе. Эта проблема связана с «персистентной» природой прологовских списков. Структура персистентных данных неизменяема и неуничтожима при манипулировании этими данными.		Соединение списков в Прологе затратно по своей природе. Эта проблема связана с «персистентной» природой прологовских списков. Структура персистентных данных неизменяема и неуничтожима при манипулировании этими данными.

	Например, если я соединяю два списка, то в результате они продолжают существовать. Способ создания объединенного списка без разрушения исходных списков, состоит в копировании первого списка в начало второго. Так, соединяя L1 и L2, мы повторно ~~ис-пользуем~~ L2 в качестве хвоста нового списка, а L1 копируется в начало нового списка. Сами элементы не копируются, копируются только ячейки списка. Поэтому затраты на соединение пропорциональны длине первого списка.		Например, если я соединяю два списка, то в результате они продолжают существовать. Способ создания объединенного списка без разрушения исходных списков, состоит в копировании первого списка в начало второго. Так, соединяя L1 и L2, мы повторно используем L2 в качестве хвоста нового списка, а L1 копируется в начало нового списка. Сами элементы не копируются, копируются только ячейки списка. Поэтому затраты на соединение пропорциональны длине первого списка.

	Используя предикат append нужно быть очень осторожным, очень легко изменить линейную сложность алгоритма (О(N)) на квадратичную (О(N*N)).		Используя предикат append нужно быть очень осторожным, очень легко изменить линейную сложность алгоритма (О(N)) на квадратичную (О(N*N)).

Victor Yukhtenko в 18:40, 21 сентября 2007

2007-09-21T18:40:35Z

← Предыдущая		Версия 20:40, 21 сентября 2007
Строка 1:		Строка 1:
	автор: Thomas Linder Puls. PDC		автор: Thomas Linder Puls. PDC

	Соединение списков ~~Пролога~~ затратно по своей природе. Эта проблема связана с «персистентной» природой ~~прологовых~~ списков. Структура персистентных данных ~~неиз-меняема~~ и неуничтожима при манипулировании с этими ~~данным~~.		Соединение списков в Прологе затратно по своей природе. Эта проблема связана с «персистентной» природой прологовских списков. Структура персистентных данных неизменяема и неуничтожима при манипулировании этими данными.
	Например, если я соединяю два списка, то в результате они продолжают ~~существо-вать~~. Способ создания объединенного списка без разрушения исходных списков, состоит в копировании первого списка в начало второго. Так, соединяя L1 и L2, мы повторно ис-пользуем L2 в качестве хвоста нового списка, а L1 копируется в начало нового списка. Сами элементы не копируются, копируются только ячейки списка. Поэтому затраты на соединение пропорциональны длине первого списка.
			Например, если я соединяю два списка, то в результате они продолжают существовать. Способ создания объединенного списка без разрушения исходных списков, состоит в копировании первого списка в начало второго. Так, соединяя L1 и L2, мы повторно ис-пользуем L2 в качестве хвоста нового списка, а L1 копируется в начало нового списка. Сами элементы не копируются, копируются только ячейки списка. Поэтому затраты на соединение пропорциональны длине первого списка.

	Используя предикат append нужно быть очень осторожным, очень легко изменить линейную сложность алгоритма (О(N)) на квадратичную (О(N*N)).		Используя предикат append нужно быть очень осторожным, очень легко изменить линейную сложность алгоритма (О(N)) на квадратичную (О(N*N)).
	Рассмотрим пример. Имеем бинарное дерево:		Рассмотрим пример. Имеем бинарное дерево:
			<vip>

	~~Код~~
	domains		domains
	binTree = empty(); tree(binTree Left, integer Node, binTree Right).		binTree =
			empty();
			tree(binTree Left, integer Node, binTree Right).
			</vip>
	Мы хотим создать список всех элементов дерева. Вот очевидный способ решения этой задачи, используя предикат append:		Мы хотим создать список всех элементов дерева. Вот очевидный способ решения этой задачи, используя предикат append:
			<vip>
			clauses
			elems(empty()) = [].
			elems(tree(Left, Node, Right)) = Elems :-
			LeftElems = elems(Left),
			RightElems = elems(Right),
			Elems = append(LeftElems, [Node\|RightElems]).
			</vip>
			Т.е. мы находим элементы в левом поддереве, затем в правом поддереве и соединяем их, вставив узел перед элементами правого поддерева.

			Это совершенно очевидный алгоритм, но очень плохой. Проблемой является левое поддерево: сначала мы создаем список всех его элементов, затем соединяем, копируя этот список перед оставшимися элементами. В наихудшем случае все дерево представляет со-бой простой путь вниз.

	~~Код~~		Если в дереве N узлов, то мы имеем одну вершину и N-1 элемен-тов в левом поддереве и пустое правое поддерево. В этом уровне, append выполнит N-1 операцию. На следующем уровне, по аналогии, будут выполнены N-2 операций, т.д. По моим представлениям о высшей математике, всего получится N*N/2 операций. Поэтому, в наихудшем случае, этот алгоритм имеет квадратичную сложность. Правда, в лучшем случае, алгоритм линейный. Оставляю вам доказательство этого утверждения.
	~~clauses~~
	~~elems(empty()) = []~~.
	~~elems(tree(Left~~, ~~Node~~, ~~Right)) = Elems :~~-
	~~LeftElems = elems(Left)~~,
	~~RightElems = elems(Right)~~,
	~~Elems = append(LeftElems~~, ~~[Node\|RightElems])~~.

			Лично я никогда не применяю append в рекурсивном алгоритме. Я использую его, например, для соединения содержимого двух списковых элементов управления. Вообще, я практически никогда не использую append. Когда я его вижу, это вызывает насторожен-ность: нет ли проблемы с этим алгоритмом?

	Т.е. мы находим элементы в левом поддереве, затем в правом поддереве и соединяем их, вставив узел перед элементами правого поддерева.
	Это совершенно очевидный алгоритм, но очень плохой. Проблемой является левое поддерево: сначала мы создаем список всех его элементов, затем соединяем, копируя этот список перед оставшимися элементами. В наихудшем случае все дерево представляет со-бой простой путь вниз. Если в дереве N узлов, то мы имеем одну вершину и N-1 элемен-тов в левом поддереве и пустое правое поддерево. В этом уровне, append выполнит N-1 операцию. На следующем уровне, по аналогии, будут выполнены N-2 операций, т.д. По моим представлениям о высшей математике, всего получится N*N/2 операций. Поэтому, в наихудшем случае, этот алгоритм имеет квадратичную сложность. Правда, в лучшем слу-чае, алгоритм линейный. Оставляю вам доказательство этого утверждения.
	Лично я никогда не применяю append в рекурсивном алгоритме. Я использую его, например, для соединения содержимого двух списковых элементов управления. Вообще, я практически никогда не использую append. Когда я его вижу, это вызывает насторожен-ность: нет ли проблемы с этим алгоритмом?
	К счастью, в нашем случае легко избежать использования append. Имеется стандарт-ная «хитрость», которая помогает решить проблему без append с линейной сложностью в худшем случае.		К счастью, в нашем случае легко избежать использования append. Имеется стандарт-ная «хитрость», которая помогает решить проблему без append с линейной сложностью в худшем случае.
	Введем вспомогательный предикат, который не только собирает узлы, но и объеди-няет их в список. Звучит это еще более сложно, чем раньше, но в действительности это не так. Вот предлагаемый предикат:		Введем вспомогательный предикат, который не только собирает узлы, но и объеди-няет их в список. Звучит это еще более сложно, чем раньше, но в действительности это не так. Вот предлагаемый предикат:
			<vip>

	~~Код~~
	clauses		clauses
	elems_append(empty(), L) = L.		elems_append(empty(), L) = L.
	elems_append(tree(Left, Node, Right), L) = M :-		elems_append(tree(Left, Node, Right), L) = M :-
	RightL = elems_append(Right, L),		RightL = elems_append(Right, L),
	M = elems_append(Left, [Node\|RightL]).		M = elems_append(Left, [Node\|RightL]).
			</vip>
			Если дерево пусто, то просто возвращается исходный список. Если дерево не пусто, то сначала присоединяем элементы правого дерева к L, затем помещаем узел в начало и, наконец, присоединяем элементы левого дерева. В результате процесс идет с конца в начало. Этот алгоритм не только не использует append, но даже в худшем случае имеет сложность О(N). Оставляю вам доказательство этого.


	Если дерево пусто, то просто возвращается исходный список. Если дерево не пусто, то сначала присоединяем элементы правого дерева к L, затем помещаем узел в начало и, наконец, присоединяем элементы левого дерева. В результате процесс идет с конца в на-чало. Этот алгоритм не только не использует append, но даже в худшем случае имеет сложность О(N). Оставляю вам доказательство этого.
	Этот предикат не решает исходной проблемы, но следующий предикат делает это:		Этот предикат не решает исходной проблемы, но следующий предикат делает это:
			<vip>

	~~Код~~
	clauses		clauses
	elem(Tree) = elem_append(Tree, []).		elem(Tree) = elem_append(Tree, []).
			</vip>

	Т.е. присоединяет пустой список к элементам дерева.		Т.е. присоединяет пустой список к элементам дерева.

Victor Yukhtenko: Новая: автор: Thomas Linder Puls. PDC Соединение списков Пролога затратно по своей природе. Эта проблема связана с «пе...

2007-09-21T18:19:16Z

Новая: автор: Thomas Linder Puls. PDC Соединение списков Пролога затратно по своей природе. Эта проблема связана с «пе...

Новая страница

автор: Thomas Linder Puls. PDC

Соединение списков Пролога затратно по своей природе. Эта проблема связана с «персистентной» природой прологовых списков. Структура персистентных данных неиз-меняема и неуничтожима при манипулировании с этими данным.
Например, если я соединяю два списка, то в результате они продолжают существо-вать. Способ создания объединенного списка без разрушения исходных списков, состоит в копировании первого списка в начало второго. Так, соединяя L1 и L2, мы повторно ис-пользуем L2 в качестве хвоста нового списка, а L1 копируется в начало нового списка. Сами элементы не копируются, копируются только ячейки списка. Поэтому затраты на соединение пропорциональны длине первого списка.
Используя предикат append нужно быть очень осторожным, очень легко изменить линейную сложность алгоритма (О(N)) на квадратичную (О(N*N)).
Рассмотрим пример. Имеем бинарное дерево:

Код
domains
binTree = empty(); tree(binTree Left, integer Node, binTree Right).

Мы хотим создать список всех элементов дерева. Вот очевидный способ решения этой задачи, используя предикат append:

Код
clauses
elems(empty()) = [].
elems(tree(Left, Node, Right)) = Elems :-
LeftElems = elems(Left),
RightElems = elems(Right),
Elems = append(LeftElems, [Node|RightElems]).

Т.е. мы находим элементы в левом поддереве, затем в правом поддереве и соединяем их, вставив узел перед элементами правого поддерева.
Это совершенно очевидный алгоритм, но очень плохой. Проблемой является левое поддерево: сначала мы создаем список всех его элементов, затем соединяем, копируя этот список перед оставшимися элементами. В наихудшем случае все дерево представляет со-бой простой путь вниз. Если в дереве N узлов, то мы имеем одну вершину и N-1 элемен-тов в левом поддереве и пустое правое поддерево. В этом уровне, append выполнит N-1 операцию. На следующем уровне, по аналогии, будут выполнены N-2 операций, т.д. По моим представлениям о высшей математике, всего получится N*N/2 операций. Поэтому, в наихудшем случае, этот алгоритм имеет квадратичную сложность. Правда, в лучшем слу-чае, алгоритм линейный. Оставляю вам доказательство этого утверждения.
Лично я никогда не применяю append в рекурсивном алгоритме. Я использую его, например, для соединения содержимого двух списковых элементов управления. Вообще, я практически никогда не использую append. Когда я его вижу, это вызывает насторожен-ность: нет ли проблемы с этим алгоритмом?
К счастью, в нашем случае легко избежать использования append. Имеется стандарт-ная «хитрость», которая помогает решить проблему без append с линейной сложностью в худшем случае.
Введем вспомогательный предикат, который не только собирает узлы, но и объеди-няет их в список. Звучит это еще более сложно, чем раньше, но в действительности это не так. Вот предлагаемый предикат:

Код
clauses
elems_append(empty(), L) = L.
elems_append(tree(Left, Node, Right), L) = M :-
RightL = elems_append(Right, L),
M = elems_append(Left, [Node|RightL]).

Если дерево пусто, то просто возвращается исходный список. Если дерево не пусто, то сначала присоединяем элементы правого дерева к L, затем помещаем узел в начало и, наконец, присоединяем элементы левого дерева. В результате процесс идет с конца в на-чало. Этот алгоритм не только не использует append, но даже в худшем случае имеет сложность О(N). Оставляю вам доказательство этого.
Этот предикат не решает исходной проблемы, но следующий предикат делает это:

Код
clauses
elem(Tree) = elem_append(Tree, []).

Т.е. присоединяет пустой список к элементам дерева.

← Предыдущая		Версия 09:20, 6 ноября 2007
Строка 3:		Строка 3:
	Соединение списков в Прологе затратно по своей природе. Эта проблема связана с «персистентной» природой прологовских списков. Структура персистентных данных неизменяема и неуничтожима при манипулировании этими данными.		Соединение списков в Прологе затратно по своей природе. Эта проблема связана с «персистентной» природой прологовских списков. Структура персистентных данных неизменяема и неуничтожима при манипулировании этими данными.

	Например, если я соединяю два списка, то в результате они продолжают существовать. Способ создания ~~объединенного~~ списка без разрушения исходных списков, состоит в копировании первого списка в начало второго. Так, соединяя L1 и L2, мы повторно используем L2 в качестве хвоста нового списка, а L1 копируется в начало нового списка. Сами элементы не копируются, копируются только ячейки списка. Поэтому затраты на соединение пропорциональны длине первого списка.		Например, если я соединяю два списка, то в результате они продолжают существовать. Способ создания объединённого списка без разрушения исходных списков, состоит в копировании первого списка в начало второго. Так, соединяя L1 и L2, мы повторно используем L2 в качестве хвоста нового списка, а L1 копируется в начало нового списка. Сами элементы не копируются, копируются только ячейки списка. Поэтому затраты на соединение пропорциональны длине первого списка.

	Используя предикат '''append''' нужно быть очень осторожным, очень легко изменить линейную сложность алгоритма (О(N)) на квадратичную (О(N*N)).		Используя предикат '''append''' нужно быть очень осторожным, очень легко изменить линейную сложность алгоритма (О(N)) на квадратичную (О(N*N)).
Строка 24:		Строка 24:
	Т.е. мы находим элементы в левом поддереве, затем в правом поддереве и соединяем их, вставив узел перед элементами правого поддерева.		Т.е. мы находим элементы в левом поддереве, затем в правом поддереве и соединяем их, вставив узел перед элементами правого поддерева.

	Это совершенно очевидный алгоритм, но очень плохой. Проблемой является левое поддерево: сначала мы ~~создаем~~ список всех его элементов, затем соединяем, копируя этот список перед оставшимися элементами. В наихудшем случае все дерево представляет ~~со-бой~~ простой путь вниз.		Это совершенно очевидный алгоритм, но очень плохой. Проблемой является левое поддерево: сначала мы создаём список всех его элементов, затем соединяем, копируя этот список перед оставшимися элементами. В наихудшем случае все дерево представляет собой простой путь вниз.

	Если в дереве N узлов, то мы имеем одну вершину и N-1 ~~элемен-тов~~ в левом поддереве и пустое правое поддерево. В этом уровне, '''append''' выполнит N-1 операцию. На следующем уровне, по аналогии, будут выполнены N-2 операций, т.д. По моим представлениям о высшей математике, всего получится N*N/2 операций. Поэтому, в наихудшем случае, этот алгоритм имеет квадратичную сложность. Правда, в лучшем случае, алгоритм линейный. Оставляю вам доказательство этого утверждения.		Если в дереве N узлов, то мы имеем одну вершину и N-1 элементов в левом поддереве и пустое правое поддерево. В этом уровне, '''append''' выполнит N-1 операцию. На следующем уровне, по аналогии, будут выполнены N-2 операций, т.д. По моим представлениям о высшей математике, всего получится N*N/2 операций. Поэтому, в наихудшем случае, этот алгоритм имеет квадратичную сложность. Правда, в лучшем случае, алгоритм линейный. Оставляю вам доказательство этого утверждения.

	Лично я никогда не применяю '''append''' в рекурсивном алгоритме. Я использую его, например, для соединения содержимого двух списковых элементов управления. Вообще, я практически никогда не использую '''append'''. Когда я его вижу, это вызывает настороженность - нет ли проблемы с этим алгоритмом?		Лично я никогда не применяю '''append''' в рекурсивном алгоритме. Я использую его, например, для соединения содержимого двух списковых элементов управления. Вообще, я практически никогда не использую '''append'''. Когда я его вижу, это вызывает настороженность - нет ли проблемы с этим алгоритмом?

	К счастью, в нашем случае легко избежать использования '''append'''. Имеется стандартная «хитрость», которая помогает решить проблему без '''append''' с линейной сложностью в худшем случае.		К счастью, в нашем случае легко избежать использования '''append'''. Имеется стандартная «хитрость», которая помогает решить проблему без '''append''' с линейной сложностью в худшем случае.
	~~Введем~~ вспомогательный предикат, который не только собирает узлы, но и объединяет их в список. Звучит это ~~еще~~ более сложно, чем раньше, но в действительности это не так. Вот предлагаемый предикат:		Введём вспомогательный предикат, который не только собирает узлы, но и объединяет их в список. Звучит это ещё более сложно, чем раньше, но в действительности это не так. Вот предлагаемый предикат:
	<vip>		<vip>
	clauses		clauses
Строка 39:		Строка 39:
	M = elems_append(Left, [Node\|RightL]).		M = elems_append(Left, [Node\|RightL]).
	</vip>		</vip>
	Если дерево пусто, то просто возвращается исходный список. Если дерево не пусто, то сначала присоединяем элементы правого дерева к L, затем помещаем узел в начало и, наконец, присоединяем элементы левого дерева. В результате процесс ~~идет~~ с конца в начало. Этот алгоритм не только не использует '''append''', но даже в худшем случае имеет сложность О(N). Оставляю вам доказательство этого.		Если дерево пусто, то просто возвращается исходный список. Если дерево не пусто, то сначала присоединяем элементы правого дерева к L, затем помещаем узел в начало и, наконец, присоединяем элементы левого дерева. В результате процесс идёт с конца в начало. Этот алгоритм не только не использует '''append''', но даже в худшем случае имеет сложность О(N). Оставляю вам доказательство этого.

	Этот предикат не решает исходной проблемы, но следующий предикат делает это:		Этот предикат не решает исходной проблемы, но следующий предикат делает это: