Ответы на экзаменационные вопросы. Введение
Скачать 389.99 Kb.
|
5.1. Сравнительные оценки алгоритмовОчевидно, что для решения некоторой массовой проблемы можно придумать не один алгоритм. Поэтому важно иметь критерии, позволяющие оценивать разработанные алгоритмы.  Время обычно интересует в наибольшей степени, поэтому именно на оценке временной сложности алгоритмов мы остановимся подробнее. Временная сложность.  Время решения индивидуальной задачи зависит от скорости вычислителя, языка программирования и многого другого. Определяя качество алгоритма имеет смысл не учитывать эти факторы. Вместо времени мы будем оценивать количество характерных операций, которое необходимо выполнить, решая индивидуальную задачу данным алгоритмом. Рассмотрим конкретную проблему (индивидуальную задачу), заданную N словами памяти. Под трудоемкостью алгоритма для данного конкретного входа – Fa(N), будем понимать количество «элементарных» операций совершаемых алгоритмом для решения конкретной проблемы в данной формальной системе. При более детальном анализе трудоемкости алгоритма оказывается, что не всегда количество элементарных операций, выполняемых алгоритмом на одном входе длины N, совпадает с количеством операций на другом входе такой же длины. Это приводит к необходимости введения специальных обозначений, отражающих поведение функции трудоемкости данного алгоритма на входных данных фиксированной длины. Пусть DА – множество индивидуальных задач (конкретных проблем) данной массовой проблемы. Пусть DDА – задание индивидуальной задач и |D| = N. Пусть DNDА – множество всех индивидуальных задач, имеющих мощность N, т.е. DN = {D DN : |D| = N}. Тогда данный алгоритм, решая различные задачи размерности N, будет выполнять в каком-то случае наибольшее количество операций, а в каком-то случае наименьшее количество операций. Можно ввести следующие обозначения (функции оценки трудоемкости): 1. Fa(N) – худший случай – наибольшее количество операций, совершаемых алгоритмом А для решения индивидуальных задач размерностью N: Fa(N) = max {Fa (D)} – худший случай на DN DDN Временной сложностью в наихудшем случае (верхней оценкой сложности алгоритма) называют функцию T(N), равную максимальному времени выполнения алгоритма для всех индивидуальных задач размером N. Часто бывает полезно определить не верхнюю оценку сложности, а среднюю, хотя это, как правило, сложнее. Точную верхнюю оценку сложности получить тоже не всегда просто. В таком случае ограничимся определением порядка роста верхней оценки временной сложности. Функция f(n) имеет порядок роста функции g(n), если найдется такая константа C, что для любых n выполняется неравенство: f(n) < C*g(n) 2. Fa(N) – лучший случай – наименьшее количество операций, совершаемых алгоритмом А для решения индивидуальных задач размерностью N: Fa(N) = min {Fa (D)} – лучший случай на DN DDN 3. Fa(N) – средний случай – среднее количество операций, совершаемых алгоритмом А для решения индивидуальных задач размерностью N: Fa(N) = (1 / |DN|)* {Fa (D)} – средний случай на DN DDN Емкостная сложность.  Тогда:  5.2. Классификация алгоритмов по виду функции трудоёмкостиВ зависимости от влияния исходных данных на функцию трудоемкости алгоритма может быть предложена следующая классификация, имеющая практическое значение для анализа алгоритмов: - Количественно-зависимые по трудоемкости алгоритмы Это алгоритмы, функция трудоемкости которых зависит только от размерности конкретного входа, и не зависит от конкретных значений: Fa (D) = Fa (|D|) = Fa (N) Примерами алгоритмов с количественно-зависимой функцией трудоемкости могут служить алгоритмы для стандартных операций с массивами и матрицами – умножение матриц, умножение матрицы на вектор и т.д. - Параметрически-зависимые по трудоемкости алгоритмы Это алгоритмы, трудоемкость которых определяется не размерностью входа (как правило, для этой группы размерность входа обычно фиксирована), а конкретными значениями обрабатываемых слов памяти: Fa (D) = Fa (d1,…,dn) = Fa (P1,…,Pm), m n Примерами алгоритмов с параметрически-зависимой трудоемкостью являются алгоритмы вычисления стандартных функций с заданной точностью путем вычисления соответствующих степенных рядов. Очевидно, что такие алгоритмы, имея на входе два числовых значения – аргумент функции и точность выполняют существенно зависящее от значений количество операций. - Количественно-параметрические по трудоемкости алгоритмы Однако в большинстве практических случаев функция трудоемкости зависит как от количества данных на входе, так и от значений входных данных, в этом случае: Fa (D) = Fa (|D|, P1,…,Pm) = Fa (N, P1,…,Pm) В качестве примера можно привести алгоритмы численных методов, в которых параметрически-зависимый внешний цикл по точности включает в себя количественно-зависимый фрагмент по размерности. - Порядково-зависимые по трудоемкости алгоритмы Среди разнообразия параметрически-зависимых алгоритмов выделим еще одну группу, для которой количество операций зависит от порядка расположения исходных объектов. Пусть множество D состоит из элементов (d1,…,dn), и |D|=N. Определим Dp = {(d1,…,dn)}-множество всех упорядоченных N-ок из d1,…,dn, отметим, что |Dp|=n!. Если Fa (iDp) Fa (jDp), где jDp Dp, то алгоритм будем называть порядково-зависимым по трудоемкости. Примерами таких алгоритмов могут служить ряд алгоритмов сортировки, алгоритмы поиска минимума и максимума в массиве. |
Похожие:
 | Ответы на экзаменационные вопросы по истории. Вопросы и ответы на экзаменационные вопросы по истории. | | Экзаменационные вопросы по культурологии А. П. Позднякова. Ботаника, Зоология, Анатомия, Общая биология конспекты уроков, лабораторные, контрольные работы, интересные статьи,... |
| Экзаменационные вопросы с ответами по физкультуре Вопросы и ответы к теоретической части экзамена по физкультуре | | Ответы на экзаменационные вопросы по литературе для 9 класса Вопросы из вариантов I и II (общеобразовательная школа, 31 и 21 билет соответственно; "старые", "Вестник образования" №4 февраль... |
| Экзаменационные билеты для 9кл. (2006) и примерные ответы по билетам... Биология урок, тест, ответы, билеты, биология человека, общая биология, егэ 2006, школа, олимпиада, тестирование биология, экзамен,... |  | Экзаменационные вопросы по бжд для студентов специальности 110203.... Экзаменационные вопросы по бжд для студентов специальности 190603. 65 – «Сервис транспортных и технологических машин и оборудования... |
| Экзаменационные вопросы по нормальной физиологии Содержит ответы на 143 экзаменационных вопроса по охране труда, а также курсы лекций по охране труда | | Экзаменационные вопросы по истории и философии науки Курс «История и философия науки» Программы курса и экзаменационные вопросы по первым двум частям курса представлены ниже |
| Экзаменационные билеты по истории России (9 класс) Девятиклассники!... Билет № Вопрос Древняя Русь в IX – начале XII в.: возникновение государства, древнерусские князья и их деятельность | | Экзаменационные вопросы интернет-курсов интуит (intuit): 192. Введение... Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования |
| Экзаменационные вопросы интернет-курсов интуит (intuit): Введение... Анооспо «Оренбургский колледж менеджмента, туризма и гостиничного сервиса» (техникум) | | Экзаменационные билеты для 9кл. (2006) и примерные ответы по билетам... А. П. Позднякова. Ботаника, Зоология, Анатомия, Общая биология конспекты уроков, лабораторные, контрольные работы, интересные статьи,... |
| Экзаменационные билеты для 9кл. (2006) и примерные ответы по билетам... А. П. Позднякова. Ботаника, Зоология, Анатомия, Общая биология конспекты уроков, лабораторные, контрольные работы, интересные статьи,... | | Содержание введение Глава I. Из истории создания религиозных учебных заведений А. П. Позднякова. Ботаника, Зоология, Анатомия, Общая биология конспекты уроков, лабораторные, контрольные работы, интересные статьи,... |
| Экзаменационные билеты по литературе для 9 класса Билет №1 «Слово о полку Игореве» На этапе окончания основной школы девятиклассники, выбравшие экзамен по литературе, сдают его, как правило, в устной форме (собеседование,... | | Ответы на экзаменационные вопросы интернет-курсов интуит (intuit): 138. Микроэкономика фирмы Администрация региона Х ввела запрет на вывоз бананов со своей территории (бананы – главный продукт потребления жителей региона).... |
