Время - работа - алгоритм
Cтраница 1
Время работы алгоритма зависит, очевидно, от его реализации. Алгоритм программируется на Алголе. Поскольку программа содержит приблизительно 300 операторов языка Алгол, мы просто проверим, как осуществляются отдельные шаги, и не формально оценим время их осуществления. [1]
Время работы алгоритма ограничено 0 ( n F), где п - число ФЗ в F. Как и в предыдущем случае, ответ зависит от порядка просмотра ФЗ. [2]
Время работы алгоритма SUMR больше, чем для базового алгоритма, но оно может окупиться повышением качества рас - -, познавания. [3]
 |
Количественные характеристики изменяемых основ словаря. [4] |
Время работы алгоритмов автоматического отождествления слов зависит от типа ЭВМ, которая используется для обработки текстовой информация, и от конкретной программной реализации этих алгоритмов. Имеет значение и объем словаря. Однако при прочих равных условиях программа морфологического анализа работает в несколько раз медленнее, чем программа отождествления слов с помощью словаря словоформ. Это обусловлено большей сложностью алгоритмов морфологического анализа и необходимостью многократного поиска по словарю при выделении основы из состава изменяемого слова. [5]
Теперь оценим время работы алгоритма в худшем случае. [6]
Чтобы установить время работы алгоритма, нам прежде всего необходимо найти верхнюю границу числа событий. [7]
Соответственно, время работы алгоритмов, основанных на полном переборе или на построении дерева решений ( методы ветвей и границ, золотого сечения и др.), растет экспоненциально в зависимости от числа вершин графа. Эти алгоритмы способны решать задачу для малого числа вершин ( п и 20) за полиномиальное время. Поэтому для решения сложных задач о коммивояжере используются различные эвристики. [8]
Сложность и время работы алгоритмов последовательно возрастают. Недостатком режима NMIN1 ( наиболее простого) является чрезмерное доверие к автоматической ранжировке. При большой избыточности исходного набора признаков такая ранжировка слабо отражает истинную значимость признаков. Алгоритм может на первых же шагах оптимизации исключить признак, который на самом деле важен для распознавания. [9]
Для подсчета времени работы алгоритма с рекурсией применяются рекуррентные уравнения. С i - й процедурой связывается функция Tf ( n), обозначающая время выполнения i - й процедуры как функцию некоторого параметра п рассматриваемого входа. Обычно рекуррентное уравнение для Тг ( п) можно записать в терминах времен выполнения процедур, вызываемых процедурой г. Затем полученная система рекуррентных уравнений решается. В следующем разделе мы изучим решения некоторых часто встречающихся систем рекуррентных уравнений. [10]
Теорема 7.10. Если время работы алгоритма А с регулярным управлением типа развертки пропорционально числу обращений к управляющему слову, то существует алгоритм распознавания управляющих слов с линейной временной оценкой. [11]
Хотя для наихудшего случая время работы алгоритма раскраски карт экспоненциально зависит от размера исходного графа, среднее время обычно весьма невелико. Однако аналитический вывод среднего значения, видимо, превышает наши возможности. Кнут описывает метод для оценки скорости работы программ, действующих по методу перебора с возвра-там и. Оценка дается вручную после просчета некоторых тестовых случаев. Кнут приводит примеры, иллюстрирующие его метод. [12]
 |
Результат операции ЧН. [13] |
Для вывода нижней оценки времени работы алгоритма 4.3 исследуем его поведение на последовательности операций НАЙТИ, за которыми следуют операции ЧН. [14]
ОБЪЕДИНИТЬ и ЧН, на которых время работы алгоритма 4.3 более чем линейно. [15]
Страницы: 1 2 3 4