Анализ рекуррентных соотношений. Мастер-теорема - История изменений

Ctrlalt: Ctrlalt переименовал страницу Асимптотический анализ рекуррентных соотношений в Анализ рекуррентных соотношений. Мастер-теорема без о…

2020-01-02T17:06:42Z

Ctrlalt переименовал страницу Асимптотический анализ рекуррентных соотношений в Анализ рекуррентных соотношений. Мастер-теорема без о…

← Предыдущая версия	Версия от 17:06, 2 января 2020
(нет различий)

Ctrlalt: /* Ссылки */

2020-01-02T17:06:01Z

Ссылки

← Предыдущая версия		Версия от 17:06, 2 января 2020
Строка 31:		Строка 31:
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%81%D1%82%D0%B5%D1%80-%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0 neerc.ifmo.ru/wiki — Мастер-теорема]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%81%D1%82%D0%B5%D1%80-%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0 neerc.ifmo.ru/wiki — Мастер-теорема]
	* [http://math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf math.dartmouth.edu — The Master Theorem]		* [http://math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf math.dartmouth.edu — The Master Theorem]
			* [http://brilliant.org/wiki/master-theorem/ brilliant.org — Master Theorem]
	* [http://www.nayuki.io/page/master-theorem-solver-javascript nayuki.io — Master theorem solver]		* [http://www.nayuki.io/page/master-theorem-solver-javascript nayuki.io — Master theorem solver]


	[[Категория:Учебный курс «Алгоритмы и структуры данных»]]		[[Категория:Учебный курс «Алгоритмы и структуры данных»]]

Ctrlalt: /* Ссылки */

2015-11-29T13:37:38Z

Ссылки

← Предыдущая версия		Версия от 13:37, 29 ноября 2015
Строка 31:		Строка 31:
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%81%D1%82%D0%B5%D1%80-%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0 neerc.ifmo.ru/wiki — Мастер-теорема]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%81%D1%82%D0%B5%D1%80-%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0 neerc.ifmo.ru/wiki — Мастер-теорема]
	* [http://math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf math.dartmouth.edu — The Master Theorem]		* [http://math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf math.dartmouth.edu — The Master Theorem]
			* [http://www.nayuki.io/page/master-theorem-solver-javascript nayuki.io — Master theorem solver]

	[[Категория:Учебный курс «Алгоритмы и структуры данных»]]		[[Категория:Учебный курс «Алгоритмы и структуры данных»]]

Ctrlalt: Новая страница: «Пусть решается задача размера ''N'', при этом рекурсивно обрабатываются ''a'' подзадач разме…»

2015-08-17T22:59:36Z

Новая страница: «Пусть решается задача размера ''N'', при этом рекурсивно обрабатываются ''a'' подзадач разме…»

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

Пусть решается задача размера ''N'', при этом рекурсивно обрабатываются ''a'' подзадач размера ''N / b'', а ответ восстанавливается из ответов на подзадачи за ''O(Nc)'' операций.

Тогда:

* На нулевом уровне дерева рекурсии имеется одна задача размера ''N'', число операций равно ''Nc'';
* На первом уровне дерева рекурсии имеются ''a'' подзадач размера ''N / b'', число операций равно ''a × (N / b)c'';
* На втором уровне дерева рекурсии имеются ''a2'' подзадач размера ''N / b2'', число операций равно ''a2 × (N / b2)c'';
* ...
* На ''i''-м уровне дерева рекурсии имеются ''ai'' подзадач размера ''N / bi'', число операций равно ''ai × (N / bi)c'';
* ...
* На ''(logbN)''-м уровне дерева рекурсии имеются ''a(logbN)'' подзадач размера 1, число операций равно ''a(logbN)''.

Общее количество операций равно ''Nc + a × (N / b)c + a2 × (N / b2)c + ... + a(logbN)'', или '''''Nc × (1 + a / bc + (a / bc)2 + ... + (a / bc)logbN)'''''.

Тогда:

* '''Если ''a / bc < 1''''', то количество операций на каждом уровне рекурсии уменьшается, геометрическая прогрессия доминируется первым членом (''O(1)''), '''асимптотическая оценка решения равна O(Nc)''''';
* '''Если ''a / bc = 1''''', то количество операций на каждом уровне рекурсии одинаково, асимптотическая оценка геометрической прогрессии линейная относительно числа членов (''O(logbN)''), '''асимптотическая оценка решения равна O(NclogN)''''';
* '''Если ''a / bc > 1''''', то количество операций на каждом уровне рекурсии увеличивается, геометрическая прогрессия доминируется последним членом (''O((a / bc)logba''), '''асимптотическая оценка решения равна''' ''O(Nc × (a / bc)logbN) = O(Nc × (Nlogba / Nc)) = '''''O(Nlogba)'''''.

Примеры:

* Двоичный поиск: ''T(N) = T(N / 2) + O(1); a = 1, b = 2, c = 0; a / bc = 1, T(N) = O(logN)'';
* Сортировка слиянием: ''T(N) = 2 × T(N / 2) + O(N); a = 2, b = 2, c = 1; a / bc = 1, T(N) = O(NlogN)'';
* Обход двоичного дерева: ''T(N) = 2 × T(N / 2) + O(1); a = 2, b = 2, c = 0; a / bc > 1; T(N) = O(N)'';
* Умножение чисел методом Карацубы: ''T(N) = 3 × T(N / 2) + O(1); a = 3, b = 2, c = 0; a / bc > 1; T(N) = O(Nlog23)'';
* Умножение матриц методом Штрассена: ''T(N) = 7 × T(N / 2) + O(1); a = 7, b = 2, c = 0; a / bc > 1; T(N) = O(Nlog27)''.

== Ссылки ==
Теория:
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%81%D1%82%D0%B5%D1%80-%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0 neerc.ifmo.ru/wiki — Мастер-теорема]
* [http://math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf math.dartmouth.edu — The Master Theorem]

[[Категория:Учебный курс «Алгоритмы и структуры данных»]]