Вычислительная сложность - алгоритм
Cтраница 1
Вычислительная сложность алгоритма ID5R на больших обучающих множествах ниже, чем у метода грубой силы, что подтверждено эмпирическим сравнением на одних и тех же обучающих выборках. Результаты сравнения даны в работе Утгоффа. [1]
Поэтому вычислительная сложность синтезируемого алгоритма обработки информации возрастает пропорционально количеству гипотез о ВИ. Следовательно, для получения наиболее простого в вычислительном отношении алгоритма следует стремиться уменьшать число рассматриваемых гипотез на каждом этапе процесса оценивания. С другой стороны, такое уменьшение, как правило, влечет за собой снижение точности вычисляемых оценок и достоверности решений, принимаемых при распознавании случайных событий. Эти ограничения сформулированы ниже в виде совокупности условий, составляющих существо установленного принципа минимальной вычислительной сложности алгоритмов распознавания-оценивания. [2]
Оценим теперь вычислительную сложность алгоритма. Циклы 22 и 25 требуют О ( я) шагов, причем для второго цикла не учитываются шаги, выполняемые при вызове ДВУСВ ( и 0) для каждой еще нерассмотренной вершины. Такой вызов для компоненты связности с п - вершинами и т - ребрами требует О ( щ - - rrii) шагов, не считая шагов в цикле 10, так как такая процедура ведет в компоненте поиск в глубину, требуя число шагов, ограниченное константой для каждого просматриваемого ребра. Каждое ребро удаляется из стека и попадает в список ребер блока в точности один раз, что дает в сумме О ( т) шагов, совершаемых циклом 10 во время его выполнения всего алгоритма. [3]
Получены оценки вычислительной сложности алгоритма и даются рекомендации по ее уменьшению. [4]
Рассмотрим оценку вычислительной сложности алгоритма IDS. [5]
Чтобы оценить вычислительную сложность алгоритма, отметим сначала, что число шагов в обоих циклах ( строки 2 и 3) порядка п, не считая шагов, выполнение которых инициировано вызовом процедуры WG. Эта процедура выполняется не более п раз во втором цикле сразу после посещения каждой из вершин для каждого из ее новых соседей, итого суммарно O ( n m) раз. [6]
 |
Машина с произвольным доступом к памяти. [7] |
Однако, чтобы понимать вычислительную сложность алгоритма, написанного на Упрощенном Алголе, мы должны соотнести Упрощенный Алгол с более формальными моделями. Это будет сделано в последнем разделе настоящей главы. [8]
Это позволяет существенно снизить вычислительную сложность алгоритма на одной итерации. Однако, возникают проблемы реализуемости БИХ-фильтра, связанные с тем, что для вычисления выходных отсчетов должны использоваться отсчеты выходного изображения, которые для наиболее часто используемых форм опорной области, как правило, еще не определены. [9]
Харт-мание, Р. Е. Стирнз, О вычислительной сложности алгоритмов, Киб. [10]
ТП, что накладывает ограничение на вычислительную сложность алгоритма. [11]
Понятие недетерминизма играет важную роль в определении вычислительной сложности алгоритмов ( С. Тьюринга способна завершить за приемлемое время такие расчеты, которые не могут быть реализованы столь же быстро никакой детерминированной машиной Тьюринга. [12]
Проведенные исследования показали, что предлагаемый принцип минимальной вычислительной сложности алгоритмов обработки информации в интеллектуальных динамических системах, функционирующих в условиях влияния внезапных возмущающих факторов, позволяет эффективно решить широкий спектр важных практических задач, в которых такие факторы имеют различную физическую природу и могут действовать как поочередно, так и одновременно. [13]
Основные понятия из теории полиномиальной сводимости дискретных задач и вычислительной сложности алгоритмов вводятся в третьем параграфе. Следует отметить, что, в отличие от первых двух, чтение третьего параграфа требует определенного уровня подготовки. Для чтения остальных глав достаточно такого понятия, как временная сложность алгоритма. [14]
Имеется перевод: Хартманис Дж, Стирнз Р, О вычислительной сложности алгоритмов. [15]
Страницы: 1 2