Линейное время

Cтраница 3

Мы видели в главе 1, что поиск максимального значения выполняется за линейное время, а редукция первой задачи ко второй тоже требует линейного времени, поэтому задачу о булевских переменных тоже можно решить за линейное время. [31]

При снижении потерь линейного времени относительно норматива каждый час должен добавлять в Фбр определенную сумму Ф % 1 в, зависящую от абсолютной величины сложившихся потерь линейного времени по данному агрегату, системе и от ее удельного веса в общих потерях линейного времени. [32]

Можно показать, что пересечение п полуплоскостей может быть найдено за время O ( nlogn) методом разделяй и властвуй, так как шаг соединения решений по своей сути есть не что иное, как задача 3.2.1, которая может быть решена за линейное время. Эта оценка является оптимальной ( см. разд. [33]

Можно показать, что пересечение п полуплоскостей может быть найдено за время О ( log га) методом разделяй и властвуй, так как шаг соединения решений по своей сути есть не что иное, как задача 3.2.1, которая может быть решена за линейное время. Эта оценка является оптимальной ( см. разд. [34]

Нелинейность такого определения fib обусловлена двумя рекурсивными вызовами в выражении в правой части третьего уравнения, порождающими двоичное дерево для представления частично вычисленных применений. Преобразованная же версия выполняется за линейное время, или, говоря более точно, требует числа вызовов функции, зависящего линейно от величины аргумента. [35]

Иллюстрация к доказатель - СТВУ те Ремы. [36]

Выпуклой оболочкой множества точек в пространстве размерности 1 является наименьший содержащий их интервал. Этот интервал может быть найден за линейное время. [37]

Данный интерфейс определяет операции над простейшим типом очереди по приоритетам: инициализировать, проверить наличие, добавить новый элемент, удалить наибольший элемент. Элементарные программные реализации этих функций обеспечивают в наихудшем случае линейное время их выполнения на массивах и списках, но в этой главе встретятся реализации, для которых время выполнения всех операций гарантировано не превосходит величины, пропорциональной логарифму количества элементов в очереди. Как обычно, параметр конструктора определяет максимальное число элементов, ожидаемых для размещения в очереди, причем некоторые реализации могут его игнорировать. [38]

Сначала будет рассмотрен случай, когда элементы, подлежащие сортировке, представлены целыми числами или ( что почти эквивалентно) словами в конечном алфавите. В этой ситуации мы увидим, что сортировку можно выполнить за линейное время. Затем изучим задачу сортировки, когда специальные свойства чисел или слов не используются и приходится строить разветвления в программе только на основе результатов сравнений сортируемых элементов. При этих условиях необходимо 0 ( п log n) сравнений; это же количество сравнений достаточно для упорядочения последовательности из п элементов. [39]

Седьмая глава посвящена рекурсии по управлению. Рассматриваются контекстно-свободные языки и автоматы с магазинной памятью, моделирование за линейное время детерминированных автоматов с магазинной памятью и с двусторонними операторами чтения, управляемый синтаксический анализ. Доказывается разрешимость проблемы эквивалентности в классе детерминированных управляемых синтаксических анализаторов с просмотром на один символ вперед. [40]

Привлекательность всех этих структурированных результатов состоит в том, что нижние оценки близки к наилучшим известным верхним оценкам1) и наилучшие известные алгоритмы могут быть реализованы на структурированных моделях, к которым относятся нижние оценки. Отметим, что корневая сортировка, про которую иногда говорят, что она требует линейного времени, на самом деле требует по крайней мере я log я шагов, если предположить, что числа на входах имеют достаточное число разрядов, чтобы все они могли быть различными. [41]

Стоимость операций, поддерживающих очередь по приоритетам, для наихудшего случая. [42]

Показатели производительности реализации АТД очереди по приоритетам колеблются в широких пределах, что следует из данной таблицы, содержащей временные показатели для наихудшего случая ( в пределах постоянного множителя для больших / V) в условиях различных методов. Элементарные методы ( первые четыре строки) требуют для выполнения некоторых операций постоянного времени и линейного времени для остальных; более совершенные методы гарантируют постоянное или линейное время выполнения для большего числа или даже для всех операций. [43]

При выводе нижней границы для алгоритма сортировки предполагалось, что алгоритм работает путем последовательного попарного сравнения элементов списка. В главе 3 мы познакомимся с другим алгоритмом сортировки ( корневая сортировка), который требует линейного времени. [44]

В действительности, несмотря на кажущуюся сложность, задача ДИАГРАММА ВОРОНОГО прекрасно подходит для применения метода разделяй и властвуй. Успех применяемого нами метода зависит от различных структурных свойств диаграммы, использование которых позволяет произвести объединение решений подзадач за линейное время. [45]

Страницы: 1 2 3 4