Студопедия

КАТЕГОРИИ:


Архитектура-(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) (вертикальная черточка здесь означает «или»). Рассмотрим функцию


= -2а + Ъ + с 3
2. Для начальной и конечной стадий имеем
 

L (a, b, c, d)

n
2)=0 соответственно.

I(n,0,0,0) = 32 n -2 и 1(0,1,1,

Каждое сравнение типов AA, BB, CC понижает значение L на 1, т.е. дает ∆ L =-1. Выпишем все возможные значения ∆ L при выпол­нении сравнений различных типов:

-1, —1 | 0, -32i-12, —2 | 0, _1 2, 0.

AA, BB, CC:
BD, CD:

AB, AC:
BC:
AD:
DD:

Сравнения, относящиеся к типам 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; Просмотров: 386; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.017 сек.