Модель ввода-вывода: различия между версиями

Перейти к навигации Перейти к поиску
Строка 19: Строка 19:


== Основные результаты ==
== Основные результаты ==
Несколько границ сложности особенно важны практически для всех алгоритмов и структур данных, эффективных с точки зрения модели ввода-вывода. ''Граница поиска'' в <math>\Theta (log_B \; n)</math> операций ввода-вывода, достижимая при использовании [[B-дерево|B-дерева]] [4], равна стоимости поиска элемента в упорядоченном наборе из n элементов, использующего только сравнения.
Несколько границ сложности особенно важны практически для всех алгоритмов и структур данных, эффективных с точки зрения модели ввода-вывода. ''Граница поиска'' в <math>\Theta (log_B \; n)</math> операций ввода-вывода, достижимая при использовании [[B-дерево (дерево многоканального поиска)|B-дерева]] [4], равна стоимости поиска элемента в упорядоченном наборе из n элементов, использующего только сравнения.