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