Cтраница 3
Подробный анализ числа сравнений в основном алгоритме выходит за рамки настоящей книги. Исследования показывают, что при поиске образца из шести или более букв в тексте на естественном языке каждый символ образца сравнивается с 40 % или менее символов текста. [31]
Однобокое двоичное поисковое дерево для множества О, 1 2, 3, 4, 5 6 7. [32] |
Очевидно, что число необходимых сравнений составляет п2 / 2 именно потому, что получается совершенно несбалансированное дерево. [33]
Некоторые проблемы, касающиеся числа сравнений, необходимых в определенных ситуациях, все еще не решены. Например, пусть требуется найти k наименьших элементов из / г-элемент-ного множества. [34]
В этой процедуре число сравнений очередного объекта с объектами упорядоченной части на единицу больше числа инверсий данного объекта со всеми объектами упорядоченного подмассива, так как сравнение происходит до первого объекта, упорядоченного с данным. [35]
Влияние длинных строк. [36] |
Рассмотрим вопрос о числе сравнений при формировании строки. [37]
На рис. 4.6 указано число сравнений, необходимых для размещения одиннадцати элементов, изображенных на рис. 4.4 и 4.5. Там же показан путь каждого элемента до соответствующей ячейки. Число сравнений при построении дерева всегда равно объему дерева. [38]
Поскольку высота дерева равна числу сравнений г: xt, которые требуется сделать в худшем случае, мы заключаем, что для таблицы с п именами бинарный поиск требует не больше f lg ( n l) - сравнений. [39]
Логическая схема реверсивного счетчика.| Схема дешифратора. [40] |
Количество заданных чисел равно числу сравнений, осуществляемых САТО, за время торможения до полной остановки стана. Дешифратор строится с помощью потенЦ Иаль-ных ячеек с диодными связями, выполняющих логическую операцию И. Диоды связываются со всеми разрядами счетчика ( рис. 5) по одной связи на каждый разряд. [41]
Однако для многих алгоритмов сортировки число сравнений является хорошей мерой производимой работы, и вследствие этого представляет интерес минимальное число сравнений, требующееся для сортировки п имен. [42]
При больших объемах исходных подмассивов число сравнений практически равно суммарному числу элементов. [43]
С ( г) равно числу сравнений на протяжении первых / проходов цикла for. Сколько же на это требуется сравнений. [44]
Кроме того, переменная п ( число сравнений с образцом) позволяет оценить эффективность алгоритма бинарного поиска по сравнению с поиском методом простого перебора. [45]