Vid1525: /* Общее описание алгоритма */

2022-10-15T11:29:41Z

Общее описание алгоритма

← Предыдущая версия		Версия от 11:29, 15 октября 2022
Строка 11:		Строка 11:

	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===
	'''Дерево отрезков''' - это упорядоченная древовидная структура данных для хранения списка точек. Эта структура позволяет эффективно сообщать результаты некоторых запросов на отрезках данного списка точек (сумма / минимум) и обычно используется в двух или более измерениях. Деревья отрезков были введены Джоном Луисом Бентли в 1979 году. Аналогичные структуры данных были обнаружены независимо Лукером, Ли и Вонгом. Дерево отрезков является альтернативой дереву k-d. По сравнению с деревьями k-d, деревья диапазонов обеспечивают более быстрое время запроса (в обозначении Big O) <math>O(log ^ dn)</math>, но худшее хранение <math>O(nlog^{d-1}n)</math>, где n - количество точек, сохраненных в дереве, d - размерность дерева.
	~~В данной работе будет рассматриваться одномерное дерево отрезков.~~

	=== Математическое описание алгоритма ===		=== Математическое описание алгоритма ===

Vid1525: initial

2022-10-15T11:13:22Z

initial

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

{{algorithm
| name = Алгоритм нахождения суммы чисел на отрезке с помощью одномерного "Дерево отрезков"
| serial_complexity = <math>O(qlog(n))</math>
| input_data = <math>n</math>
| output_data = <math>q</math>
}}

Авторы: [[Участник:vid1525_1864|И.Д. Васенков]]

== Свойства и структура алгоритма ==

=== Общее описание алгоритма ===
'''Дерево отрезков''' - это упорядоченная древовидная структура данных для хранения списка точек. Эта структура позволяет эффективно сообщать результаты некоторых запросов на отрезках данного списка точек (сумма / минимум) и обычно используется в двух или более измерениях. Деревья отрезков были введены Джоном Луисом Бентли в 1979 году. Аналогичные структуры данных были обнаружены независимо Лукером, Ли и Вонгом. Дерево отрезков является альтернативой дереву k-d. По сравнению с деревьями k-d, деревья диапазонов обеспечивают более быстрое время запроса (в обозначении Big O) <math>O(log ^ dn)</math>, но худшее хранение <math>O(nlog^{d-1}n)</math>, где n - количество точек, сохраненных в дереве, d - размерность дерева.
В данной работе будет рассматриваться одномерное дерево отрезков.

=== Математическое описание алгоритма ===
=== Вычислительное ядро алгоритма ===
=== Макроструктура алгоритма ===
=== Схема реализации последовательного алгоритма ===
=== Последовательная сложность алгоритма ===
=== Информационный граф ===
=== Ресурс параллелизма алгоритма ===
=== Входные и выходные данные алгоритма ===
=== Свойства алгоритма ===
== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

Sqlite https://www.sqlite.org/

SciPy https://scipy.org/

Sklearn https://scikit-learn.org/stable/

== Литература ==

1. Bentley, J. L. (1979). "Decomposable searching problems".

2. Lueker, G. S. (1978). "A data structure for orthogonal range queries". 19th Annual Symposium on Foundations of Computer Science (sfcs 1978).

3. Lee, D. T.; Wong, C. K. (1980). "Quintary trees: A file structure for multidimensional database systems". ACM Transactions on Database Systems.

#[[Категория:Алгоритмы и структуры данных]]

Участник:Vid1525 - История изменений

Vid1525: /* Общее описание алгоритма */

Vid1525: initial