Время - выполнение - алгоритм
Cтраница 3
Абсолютные цифры, характеризующие время выполнения сравниваемых алгоритмов, очень сильно зависят от вычислительной системы, на которой эти алгоритмы выполняются. Программы, осуществляющие удаление невидимых линий должны были конкурировать с большим числом других пользователей системы разделения времени. [31]
После того как мы установили существование ( возможно, бесконечных1)) алгоритмов, которые являются оптимальными в сильном смысле, выясним, насколько они хороши на самом деле. В относительном смысле они минимизируют среднее значение г-й степени времени выполнения алгоритма при всех г. Оказывается, что они всегда хороши и в абсолютном смысле, по крайней мере в среднем: какое бы распределение мы не рассматривали, после небольшой начальной задержки результат производится с такой же скоростью, с какой данные поступают на вход алгоритма. [32]
Возможно, рекурсии нельзя избежать еще потому, что рекурсивный алгоритм Фибоначчи ограничен скорее вычислением слишком большого количества промежуточных значений, чем глубиной рекурсии. Удаление хвостовой рекурсии уменьшает глубину рекурсии, но это не изменяет время выполнения алгоритма. Даже без хвостовой рекурсии он все равно будет чрезвычайно медленным. [33]
Необходимо различать два пути повышения эффективности программ - улучшение кода и улучшение алгоритма. Эффективность в смысле теории сложности часто рассматривается в качестве асимптотического приближения времени выполнения алгоритма. [34]
Напомним, что главное предназначение указателя р ( х) состоит в том, что он должен нам сообщать, принадлежат или нет вершины ж и у, являющиеся вершинами цветков, одному и тому же цветку. Однако повторное вычисление указателя р ( х) всякий раз, когда это требуется, добавляет сомножитель р ко времени выполнения алгоритма. [35]
Соответствующий алгоритм должен поддерживать некоторое представление текущей выпуклой оболочки и корректировать его по мере поступления точек. Вопрос состоит в том, можно ли сделать это, не принося в жертву оценку 0 ( N ogN) времени выполнения алгоритма, необходимого на обработку всего множества точек. [36]
Каждая величина имеет имя, значение и тип. Имя величины ( например, n, х, d) служит для обозначения величины в алгоритме. Во время выполнения алгоритма в каждый конкретный момент величина имеет какое-то значение ( например, 22 или - 107) либо не определена. Если значением величины может быть только целое число, то величина называется целой или целочисленной, если любое вещественное число - то вещественной. Эта характеристика величины ( в данном случае является ли величина целой или вещественной) называется типом величины. Обычно кроме числовых величин в языке программирования есть величины и других типов: логические, литерные и другие. [37]
Рекурсивное разбиение алгоритма напрямую проявляется в его анализе. Например, время выполнения подобных алгоритмов определяется величиной и номером подзадачи, а также временем, необходимым для разбиения задачи. Математически зависимость времени выполнения алгоритма для ввода величиной N от времени выполнения при меньшем количестве вводов легко задается с помощью рекуррентных соотношений. Такие формулы точно описывают производительность алгоритмов: для вычисления времени выполнения необходимо решить эти рекурсии. [38]
Например, представим себе компанию, обрабатывающую кредитные карточки и имеющую N рискованных или украденных кредитных карточек. При этом компании необходимо проверять, нет ли среди М транзакций какого-либо из этих TV плохих номеров. Цель анализа заключается в приблизительной оценке времен выполнения алгоритмов, когда параметры принимают значения из указанного диапазона. [39]
Более точно, но и трудоемко можно оценить Ур аналитическими методами. Вычислительный процесс представляется в виде графа, в вершинах которого располагают алгоритмические действия У /; ребра графа характеризуют связи между ними. Граф удобен также и для оценки времени выполнения алгоритма, что необходимо при определении возможности реализации алгоритма в реальном времени в конкретной АИИС с данной ЭВМ или при выборе ЭВМ. При этом может быть оценено как максимальное, так и среднее время, что позволяет более эффективно загрузить ЭВМ. Оценка среднего времени выполнения алгоритма проводится с помощью микс-характе-ристик ЭВМ. [40]
Она применима к любому рекурсивному вычислению при условии, что мы можем себе позволить хранить все ранее вычисленные значения. Такая технология разработки алгоритмов успешно используется для решения широкого круга задач. Поэтому следует уделить внимание простой технологии, которая может изменить зависимость времени выполнения алгоритма от значения аргументов с экспоненциальной на линейную. [41]
Таким образом, зависимость отношения O ( N) отизмененияразмеразадачи более очевидна. Если увеличить N в 2 раза, эта двойка возводится в квадрат ( N) и время выполнения алгоритма увеличивается в 4 раза. [42]
Характеризуя назначение ЭВМ, указывают не только класс алгоритмов ( задач), выполнение которых является функцией ЭВМ, но и требования к производительности и надежности ЭВМ. Производительность определяется числом задач, решаемых ЭВМ в единицу времени, и для достижения требуемой производительности ЭВМ приходится наделять специальными функциями, обеспечивающими, например, параллельную обработку нескольких задач. Таким образом, существенное влияние на организацию ЭВМ оказывают не только свойства алгоритмов, но и требования к производительности - времени выполнения алгоритмов. [43]
 |
Оценочные элементы фактора надежность ПО ( выборка из ГОСТ 28195 - 89. [44] |
Могут быть получены также другие показатели, например, частота отказов ПТС из-за ошибок в ПО, средняя наработка до отказа ПТС из-за ошибок в ПО и др. В дальнейшем из-за трудностей получения оценок максимального правдоподобия эта модель была развита для получения Байесовских оценок указанных параметров. Эта модель названа моделью BJM. Модель Sooman [10] практически идентична модели JM, a Musa [11] использовал JM для более совершенной модели, включающей как календарное время, так и время выполнения алгоритма отдельных компонентов ПО. [45]
Страницы: 1 2 3 4