КАТЕГОРИИ: Архитектура-(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) |
АА: (а-2, b + 1,c + 1,d), АВ: (a-1,b,c + 1,d)|(a АС: (а-1, b + 1,c,d)|(a AD: (а- 1, Ъ + 1, с, d) | (а
BB: (a, b - 1, c, d + 1), BC: (a, b - 1, c - 1, d + 2) | (a, b, c, d), BD: (a, b - 1, c, d + 1) | (a, b, c, d), CC: (a, b, c - 1, d + 1), CD: (a, b, c - 1, d + 1) | (a, b, c, d), DD: (a, b, c, d) (вертикальная черточка здесь означает «или»). Рассмотрим функцию
L (a, b, c, d)
I(n,0,0,0) = 32 n -2 и 1(0,1,1, Каждое сравнение типов AA, BB, CC понижает значение L на 1, т.е. дает ∆ L =-1. Выпишем все возможные значения ∆ L при выполнении сравнений различных типов:
AA, BB, CC: AB, AC: Сравнения, относящиеся к типам AB, AC, BC, могут приводить к ∆ L < -1, но это не может быть гарантировано никаким специальным выбором элементов из соответствующих множеств четверки 112 Глава 4. Нижняя граница сложности. Оптимальные алгоритмы (A, B, C, D), даже если принимать во внимание результаты всех сравнений, в которые были вовлечены конкретные элементы этих множеств. Например, сравнение типа AB в том случае, когда выбранный элемент из A оказывается больше выбранного элемента из B, преобразует (a, b, c, d) в (a - 1, b,c,d + 1), что дает Д L < -1. Но результаты предшествующих сравнений не дают оснований для отметания возможности того, что выбранный элемент из B равен шах{ x 1, x2, •••, xn} (ибо этот элемент оказался большим во всех сравнениях, в которые он был вовлечен). Но тогда будет выполнено Д L = -12. Аналогичным образом дело обстоит для сравнений, принадлежащих типам AC, BC. Поэтому, рассматривая поведение алгоритма V в худшем случае, надо считать, что на всех этапах Д L ^ - 1. Но тогда для достижения равенства L(a, b, c, d) = 0 потребуется не менее \L(n, 0, 0, 0)1 сравнений. Это значит, что общее число сравнений в худшем случае не меньше,
чем - n - 2. □ Представленный в приложении A алгоритм одновременного поиска наибольшего и наименьшего элементов массива, требующий в худшем случае не более -2 - 2 сравнений, является оптимальнымг. Наряду с алгоритмами поиска наименьшего элемента, бинарного поиска места элемента в упорядоченном массиве и алгоритма одновременного поиска наибольшего и наименьшего элементов массива примером оптимального алгоритма может служить алгоритм («схема») Горнера вычисления значения полинома в данной точке (см. приложение D). Для произвольного класса .s4 оптимальный алгоритм может и не существовать: если, например, .s4 содержит ровно два алгоритма, A1,A2, и при этом A1 имеет низкую сложность при четных значениях целочисленного размера входа n и высокую — при нечетных, а A2 — наоборот, то, очевидно, ни A1, ни A2 не будут оптимальными в .s4. Ясно, что если оптимальные алгоритмы в классе .s4 существуют, то их сложности совпадают: из неравенств TA (n) ^ TA (n) и TA 2 (n)^TA 1 (n) следует, что TA 1 (n) = TA 2 (n). Несколько более содер-жательный пример можно найти в задаче 76. В отличие от поиска наименьшего элемента, поиска места в упорядоченном массиве и одновременного поиска наибольшего и наи- 1 Этот алгоритм и идея использования четверок (A, B, C, D) в доказательстве его оптимальности были предложены И. Полом в [56], но при этом убывающие функции в его доказательстве не привлекались, из-за чего потребовались дополнительные словесные мотивации. § 15. Оптимальные алгоритмы меньшего элементов, задача сортировки не столь проста: те алгоритмы, которыми пользуются на практике для ее решения, не являются, строго говоря, оптимальными (см. приложение F). Заметим при этом, что для каждого конкретного п за конечное число шагов может быть найдено наименьшее число сравнений, достаточное в худшем случае для сортировки п элементов, а вместе с ним и алгоритм сортировки с такой сложностью. Это следует из того, что при каждом конкретном п алгоритм сортировки может быть представлен бинарным деревом. Можно порождать одно за другим все бинарные деревья с высотой, не превосходящей [log2 n!l, в вершинах каждого такого дерева различными способами расставлять выражения вида xt<Xj, где i,j^n, а в листьях — различные перестановки длины п. Для каждого размеченного таким способом дерева нужно проверить, действительно ли каждая ветвь приводит именно к тому порядку, который указан в листе, и что все возможные порядки охвачены. Из всех «правильных» деревьев выбирается имеющее наименьшую высоту. Оно определяет оптимальный алгоритм для заданного п.
Таким образом, мы имеем алгоритм, который, исходя из п > 0, строит оптимальный по числу сравнений алгоритм сортировки массивов из п элементов (алгоритм строит алгоритм). Этот алгоритм построения оптимального алгоритма сортировки требует огромной работы, даже если применить все средства экономии перебора. Этот пример еще раз показывает, что понятие алгебраической сложности требует осторожного обращения, —объем неучитываемых операций может превзойти разумные пределы. Бинарный алгоритм возведения в степень п также не является оптимальным по числу умножений при использовании п в качестве размера входа (см. задачу 19), хотя и легко показать, что для случая п = 2к при рассмотрении к в качестве размера входа оптимальность имеет место: из предложения 14.5 следует, что возведение в степень п = 2к не может быть выполнено с затратами меньшими, чем к умножений, а бинарный алгоритм обходится в точности этим числом умножений. В общем же случае, как и многие известные алгоритмы сортировки, бинарный алгоритм возведения в степень оптимален лишь в некотором асимптотическом смысле, о чем пойдет речь в следующем параграфе. Если затраты для каждого входа являются целыми числами (например, они являются количеством выполненных операций), то для фиксированного размера п0 входа в рассматриваемом классе .s4 ал- 114 Глава 4. Нижняя граница сложности. Оптимальные алгоритмы горитмов решения некоторой задачи P существует такой, сложность которого при n = n0 есть минимум сложностей всех алгоритмов из .s4. Можно определить такой минимум для любого значения n, получаемую таким способом функцию от n иногда называют сложностью задачи P по отношению к классу алгоритмов .s4. Важно, что при разных n минимумы могут доставляться разными алгоритмами из .s4 (см. задачу 76). В дальнейшем мы не будем касаться этих вопросов.
Дата добавления: 2014-01-11; Просмотров: 398; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |