КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Система обозначений в анализе алгоритмов
При более детальном анализе трудоемкости алгоритма оказывается, что не всегда количество элементарных операций, выполняемых алгоритмом на одном входе длины N, совпадает с количеством операций на другом входе такой же длины. Это приводит к необходимости введения специальных обозначений, отражающих поведение функции трудоемкости данного алгоритма на входных данных фиксированной длины. Пусть D А — множество конкретных проблем данной задачи, заданное в формальной системе. Пусть DҒ, D А — задание конкретной проблемы и |D|=N. В общем случае существует собственное подмножество множества D А, включающее все конкретные проблемы, имеющие мощность N: - обозначим это подмножество через DN:D N= {DҒ, DN: |D| = N}; - обозначим мощность множества DN через MDN → MDN=|DN |. Тогда содержательно данный алгоритм, решая различные задачи размерности N, будет выполнять в каком-то случае наибольшее количество операций, а в каком-то случае наименьшее количество операций. Введем следующие обозначения: 1. F α ^(N) - худший случай - наибольшее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N: F α ^(N) = max { F α (D)} DDN -худший случай на DN. 2. F α (N) - лучший случай - наименьшее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N: Fa (N) = min {Fa (D)} DDN - лучший случай на DN 3. α(N) - средний случай - среднее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N: a(N)=(1/MDN}·Σ{Fa(D)} DÎDN - средний случай на DN 3. Классификация алгоритмов по виду функции трудоёмкости В зависимости от влияния исходных данных на функцию трудоемкости алгоритма может быть предложена следующая классификация, имеющая практическое значение для анализа алгоритмов: 1. Количественно-зависимые по трудоемкости алгоритмы Это алгоритмы, функция трудоемкости которых зависит только от размерности конкретного входа, и не зависит от конкретных значений: Fa(D) = Fa (|D|)= Fa(N) Примерами алгоритмов с количественно-зависимой функцией трудоемкости могут служить алгоритмы для стандартных операций с массивами и матрицами - умножение матриц, умножение матрицы на вектор и т.д. 2.Параметрически-зависимые по трудоемкости алгоритмы Это алгоритмы, трудоемкость которых определяется не размерностью входа (как правило, для этой группы размерность входа обычно фиксирована), а конкретными значениями обрабатываемых слов памяти: Fa(D) = Fa(d1,..,dn) = Fa(P1,..,Pm),m=<n Примерами алгоритмов с параметрически-зависимой трудоемкостью являются алгоритмы вычисления стандартных функций с заданной точностью путем вычисления соответствующих степенных рядов. Очевидно, что такие алгоритмы, имея на входе два числовых значения - аргумент функции и точность выполняют существенно зависящее от значений количество операций. а) Вычисление xkпоследовательным умножением Þ Fa(x,k) = Fa(k). б) Вычисление e x=Σ(x-n/n!), с точностью до ξ => Fa= Fa(х,ξ) 3. Количественно-параметрические по трудоемкости алгоритмы Однако в большинстве практических случаев функция трудоемкости зависит как от количества данных на входе, так и от значений входных данных, в этом случае: Fa(D) = Fa(||D||,P1,..,Pm)=Fa(N,P1,..,Pm) В качестве примера можно привести алгоритмы численных методов, в которых параметрически-зависимый внешний цикл по точности включает в себя количественно-зависимый фрагмент по размерности. 3.1 Порядково-зависимые по трудоемкости алгоритмы Среди разнообразия параметрически-зависимых алгоритмов выделим еще оду группу, для которой количество операций зависит от порядка расположения исходных объектов. Пусть множество D состоит из элементов (d1,...,dn), и ||D||=N, Определим Dp = {(d1,...,dn)}-множество всех упорядоченных N-ок из d1,...,dn, отметим, что |Dp|=n!. Если Fa(iDp)≠Fa(jDp), где iDp, jDp, ғDp, то алгоритм будем называть порядково-зависимым по трудоемкости. Примерами таких алгоритмов могут служить ряд алгоритмов сортировки, алгоритмы поиска минимума и максимума в массиве. Рассмотрим более подробно алгоритм поиска максимума в массиве S, содержащим n элементов: MaxS(S,n; Мах) Max← S1 For i←2 to n If Max <Si Then Max←Si (количество выполненных операций присваивания зависит от порядка следования элементов массива)
Дата добавления: 2014-11-20; Просмотров: 527; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |