Трудоемкость - алгоритм
Cтраница 2
 |
К вычислению дисперсии трудоемкости алгоритма. [16] |
Прикладные методы оценки сложности вычислений ( трудоемкости алгоритмов, времени выполнения алгоритмов) изложены во многих статьях. Основополагающие вероятностные модели машинных программ были разработаны К. Во всех указанных работах рассматриваются способы вычисления среднего времени выполнения алгоритмов. [17]
Обозначим через Т ( т) трудоемкость алгоритма построения выпуклой оболочки для множества из т точек. [18]
Количество вычислений, проводимых при расчете трудоемкости алгоритмов, можно значительно сократить, если использовать сетевой подход к анализу трудоемкости последних: Такой подход особенно удобен, когда анализ алгоритмов проводится вручную, к тому же он позволяет получать среднюю, минимальную и максимальную трудоемкость. [19]
Класс PR - класс параметрически зависимых по трудоемкости алгоритмов. [20]
Из проведенных выше рассуждений следует, что асимптотическая трудоемкость алгоритма линейного решета ( 12), определяется трудоемкостью аддитивных операций в процедуре модификации массива МС1, которая асимптотически превосходит трудоемкость обобщенного алгоритма Евклида. [21]
Как уже отмечалось несколько раз в этой главе, вычислительная трудоемкость алгоритмов тесно связана с количеством целочисленных переменных, входящих в задачу. В данном алгоритме объем вычислений определяется прежде всего числом задач, входящих в основной список. [22]
Этот эффект объясняется наличием большой мультипликативной константы в оценке трудоемкости алгоритма решета числового поля. [23]
Количество действий, выполняемых в процессе вычислений, определяется трудоемкостью алгоритма, и если три построении модели вычислительного процесса исходить только из сведений о трудоемкости алгоритма, то степень приближения модели к реальным процессам целиком определяется полнотой и достоверностью сведений о трудоемкости алгоритма. [24]
Несмотря на достаточно простые подходы к анализу основных алгоритмических конструкций, получение функций трудоемкости алгоритмов остается достаточно сложной задачей, требующей применения специальных подходов и методов, а иногда и введения специальных функций. [25]
Для обеспечения необходимой точности решения некоторых задач анализа ВС необходимы сведения о дисперсии трудоемкости алгоритма. Дисперсия характеризует степень разброса значений случайной величины относительно своего среднего значения и чем больше дисперсия, тем больше разброс значений. [26]
Поскольку в задаче выбора диспетчерских правил используются две переменные состояния и четыре варьируемые переменные, существенную роль играют проблемы вычислительной трудоемкости алгоритма оптимизации. Этот выбор определяется пределами допустимого изменения указанных величин. С целью ускорения вычислений предлагается схему оптимизации динамического программирования погрузить внутрь некоторого итеративного процесса последовательного уточнения решений. Если на первом этапе такого процесса назначаются широкие пределы допустимого изменения всех величин с разбиением их на шаги дискретности А, Az, Az, Аг. Az, то эти шаги первоначально будут достаточно грубые. По результатам первого этапа не только выявятся сугубо приближенные решения задачи, но и определятся фактические более узкие пределы изменения упомянутых величин. Если принять эти новые пределы изменения величин и заново провести процедуру дискретного поиска и сужения пределов изменения, то, повторив оптимизационный расчет, можно на втором этапе получить уточненные решения. Во всех случаях, проведение серии уточняющих расчетов оказывается с вычислительных позиций выгоднее детальной оптимизации за один этап. [27]
Поскольку в задаче выбора диспетчерских правил используются две переменные состояния и четыре варьируемые переменные, существенную роль играют проблемы вычислительной трудоемкости алгоритма оптимизации. Этот выбор определяется пределами допустимого изменения указанных величин. С целью ускорения вычислений предлагается схему оптимизации динамического программирования погрузить внутрь некоторого итеративного процесса последовательного уточнения решений. Если на первом этапе такого процесса назначаются широкие пределы допустимого изменения всех величин с разбиением их на шаги дискретности Agft, А 2, Az, Az t AQii и Az, то эти шаги первоначально будут достаточно грубые. По результатам первого этапа не только выявятся сугубо приближенные решения задачи, но и определятся фактические более узкие пределы изменения упомянутых величин. Если принять эти новые пределы изменения величин и заново провести процедуру дискретного поиска и сужения пределов изменения, то, повторив оптимизационный расчет, можно на втором этапе получить уточненные решения. Во всех случаях, проведение серии уточняющих расчетов оказывается с вычислительных позиций выгоднее детальной оптимизации за один этап. [28]
За счет простоты аппроксимаций формы расчетных гидрографов (11.2.10), (11.2.11) и сбросных расходов (11.6.9), а также вследствие невысокой требуемой точности, вычислительная трудоемкость алгоритма в целом невелика. На компьютерах класса Pentium для 10 - 15 вершин в графе Т ( 7, S ] решение задачи в описанном виде не превышает 0 5 - 2 минуты без учета динамической составляющей напора и 3 - 12 минут при ее учете. [29]
За счет простоты аппроксимаций формы расчетных гидрографов (11.2.10), (11.2.11) и сбросных расходов (11.6.9), а также вследствие невысокой требуемой точности, вычислительная трудоемкость алгоритма в целом невелика. На компьютерах класса Pentium для 10 - 15 вершин в графе Т ( J, S) решение задачи в описанном виде не превышает 0 5 - 2 минуты без учета динамической составляющей напора и 3 - 12 минут при ее учете. [30]
Страницы: 1 2 3 4