Сложность - алгоритм
Cтраница 3
Если под сложностью алгоритма понимать время поиска, этот подход обладает тем лее недостатком, что и первый, но плюс к этому добавляется трудность программирования для машин Тьюринга. [31]
Если интересоваться сложностью алгоритмов с точностью до полиномиально ограниченного множителя, многоленточные машины ничего не добавляют по сравнению с описанными выше машинами с единственной лентой. [32]
Если под сложностью алгоритма понимать время поиска, этот подход обладает тем же недостатком, что и первый, но плюс к этому добавляется трудность программирования для машин Тьюринга. [33]
Теория сложности изучает сложность алгоритмов. Существует несколько способов измерения сложности алгоритма. Программисты обычно сосредотачивают внимание на скорости алгоритма, но не менее важны идругие показатели - требования к объему памяти, свободному месту на диске. Использование быстрого алгоритма не приведет к ожидаемым результатам, если для его работы понадобится больше памяти, чем есть у вашего компьютера. [34]
Рекуррентные соотношения на сложность алгоритма выводятся непосредственно из вида алгоритма, однако с их помощью нельзя быстро вычислить эту сложность. Для этого следует привести рекуррентные соотношения к так называемому замкнутому виду, отказавшись от их рекуррентной природы. Производится такое приведение посредством последовательных подстановок, позволяющих уловить общий принцип. [35]
 |
Зависимость временной и пространственной сложности алгоритма от числа вершин. [36] |
Здесь ПСА - пространственная сложность алгоритма, определяемая объемом оперативной памяти при работе алгоритма. В течение одного поколения выполняется один оператор селекции и один ОК. ОМ выполняются не чаще одного раза в 4 - 5 поколений. Необходимо учесть, что при начальной генерации популяции формирование одной хромосомы требует L операций для определения генов. После генерации начальной популяции необходимо выполнить ее сортировку, что требует Np log 2NP операций. То есть, временная сложность генетического алгоритма составит: О ( ( п т) 2т [ Nplog2Np ( Np 2log2Np) O ( L ] O ( L) / 5 ] NG), где NG - число поколений, Np - размер популяции. [37]
 |
Структурная схема измерения. [38] |
Следует отметить и сложность алгоритма обработки сигнала. На рис. 3.11 показана только схема для получения t / misin. Аналогичная схема необходима для получения Umlcos. Элементы расчета по этой формуле не показаны на рисунке. Требуются еще дополнительные элементы, ради упрощения не показанные на схеме. [39]
Двумя важными мерами сложности алгоритма являются временная и емкостная сложности, рассматриваемые как функции размера входа. Если при данном размере в качестве меры сложности берется наибольшая из сложностей ( по всем входам этого размера), то она называется сложностью в худшем случае. Если в качестве меры сложности берется средняя сложность по всем входам данного размера, то она называется средней ( или усредненной) сложностью. [40]
В результате анализа сложности алгоритма мы получаем асимптотическую оценку ( или порядок алгоритма см. 1.4.1. основного текста) для количества задаваемых им операций. Зная такие оценки для разных алгоритмов решения определенной задачи, мы получаем возможность сравнить эти алгоритмы с точки зрения их эффективности. Однако асимптотические оценки указывают не более чем порядок функции, и результаты сравнения будут справедливы только при очень больших размерах входа. [41]
С точки зрения сложности алгоритмов испытаний можно выделить три основных уровня испытаний: параметрическая идентификация, структурная идентификация и имитационное моделирование узлов или физических процессов. [42]
Аналогично вводят определение сложности алгоритма ср. Эту сложность сотр ( ф) называют комбинаторной, и в ней не учтены информационный оператор и заданная погрешность решения. [43]
Число г называется мультипликативной сложностью билинейного алгоритма. [44]
Приведенные в таблицах оценки сложности алгоритмов справедливы в предположении, что отношение строгого порядка, заданное на множестве требований ( если оно не пусто), представлено своим графом редукции. Отметим, что переход от произвольного бесконтурного графа к его транзитивному замыканию или к графу редукции требует выполнения не более 0 ( п3) операций [7], где п - число вершин графа. [45]
Страницы: 1 2 3 4