Структуры данных и алгоритмы (1021739), страница 68
Текст из файла (страница 68)
Какова вэтом случае будет временная сложность процедуры построения частично упорядоченного дерева?*8.9. Допустим, что есть множество слов, т.е. строк, состоящих из букв а - г. Суммарная длина слов равна п. Покажите, что эти слова можно упорядочить завремя О(п). Отметим, что для слов одинаковой длины можно применить"карманную" сортировку.
Но вы также должны предусмотреть случай словразной длины.*8.10. Покажите, что для сортировки вставками среднее время выполнения неменьше Щп2).**8.11. Рассмотрим алгоритм случайной сортировки, примененный к массиву А[1..га]целых чисел: выбирается случайное число i из интервала от 1 до л и меняютсяместами элементы А[1] и A[i], процесс повторяется до тех пор, пока не будутупорядочены все элементы массива. Каково ожидаемое время выполнения этойсортировки?*8.12. В разделе 8.6 было показано, что сортировки, выполняемые посредством сравнений, в самом худшем случае требуют Ci(n logn) сравнений. Покажите, чтоэта нижняя граница справедлива и в среднем.*8.13. Докажите, что процедура select, неформально описанная в начале раздела 8.7,имеет среднее время выполнения О(п).8.14. Реализуйте оператор конкатенации CONCATENATE для структуры данных,показанной на рис.
8.4.8.15. Напишите программу нахождения k наименьших элементов в массиве длиной п. Какова временная сложность этой программы? Для каких значений kэффективнее сначала выполнить сортировку всего массива, а затем взять kнаименьших элементов, вместо поиска наименьших элементов в неупорядоченном массиве?8.16. Напишите программу нахождения наибольшего и наименьшего элементов вмассиве.
Может ли эта программа обойтись менее чем 2га — 3 сравнениями?8.17. Напишите программу нахождения моды (наиболее часто встречаемого элемента) в списке из п элементов. Какова временная сложность этой программы?*8.18. Покажите на модели дерева решений из раздела 8.6, что любой алгоритмудаления дублирующих записей из заданного списка требует времени неменее il(ra logra).*8.19.
Предположим, что есть k множеств St, S2S4, каждое из которых состоитиз га действительных чисел. Напишите программу получения списка всех суммвида Sj + s2 + ... + «ь где s( принадлежит отсортированному множеству St. Какова временная сложность этой программы?8.20. Предположим, есть сортированный массив строк s t , s2, ..., sn. Напишите программу, определяющую, является ли предъявленная строка ж членом этой последовательности. Какова временная сложность этой программы как функцииот п и длины строки xlУПРАЖНЕНИЯБиблиографические примечанияМонография [65] является исчерпывающим обзором по методам сортировки. Метод быстрой сортировки предложен Хоаром (Ноаге) [49], более поздние вариантыэтой сортировки приведены в [37] и [103]. Пирамидальная сортировка была открытаВильямсом (Williams) [119] и обоснована Флойдом (Floyd) [34].
Сложность дереварешений для сортировки изучалась в работе [36]. Линейный алгоритм сортировки израздела 8.7 взят из статьи [13].Алгоритм Шелла описан в [101], анализ его выполнения приведен в работе [87].См. также книгу [3], где приведено одно решение упражнения 8.9.264ГЛАВА 8. СОРТИРОВКАГЛАВА 9Методы анализа алгоритмовЧто собой представляет "хороший" алгоритм? Не существует простого ответа на этотвопрос. Многие оценки алгоритмов включают такие субъективные понятия, как простота, понятность или соответствие ожидаемым входным данным. Более объективной(но, возможно, не самой важной) оценкой алгоритма может служить временнаяэффективность (время выполнение) алгоритма.
В разделе 1.5 описывались основныеметоды определения времени выполнения простых программ. Но в более сложныхситуациях, например при оценке рекурсивных программ, необходимы другие методы. В этой короткой главе рассмотрены некоторые достаточно общие методы решения рекуррентных соотношений, которые возникают при анализе времени выполнения рекурсивных алгоритмов.9.1.
Эффективность алгоритмовОдин из способов определения временной эффективности алгоритма заключаетсяв следующем: на основе данного алгоритма надо написать программу и измеритьвремя ее выполнения на определенном компьютере для выбранного множества входных данных. Хотя такой способ популярен и, безусловно, полезен, он порождает определенные проблемы. Определяемое здесь время выполнения зависит не только отиспользуемого алгоритма, но также от архитектуры и набора внутренних инструкций данного компьютера, от качества компилятора, да и от уровня программиста,реализовавшего тестируемый алгоритм.
Время выполнения также может существенно зависеть от выбранного множества тестовых входных данных. Эта зависимостьстановится совершенно очевидной при реализации одного и того же алгоритма с использованием различных компьютеров, различных компиляторов, при привлечениипрограммистов разного уровня и при использовании различных тестовых входныхданных.
Чтобы повысить объективность оценок алгоритмов, ученые, работающие вобласти компьютерных наук, приняли асимптотическую временную сложность какосновную меру эффективности выполнения алгоритма. Термин эффективность является синонимом этой меры и относится в основном к времени выполнения в самомхудшем случае (в отличие от среднего времени выполнения).Напомним читателю определения О(/(л)) и £l(f(n)), данные в главе 1. Говорят, чтоалгоритм имеет эффективность (т.е.
временною сложность в самом худшем случае)O(f(n)), или просто f(n), если функция от п, равная максимуму числу шагов, выполняемых алгоритмом, имеет порядок роста О(/(га)), причем максимум берется по всемвходным данным длины п. Можно сказать по-другому: существует константа с, такая, что для достаточно больших п величина cf(n) является верхней границей количества шагов, выполняемых алгоритмом для любых входных данных длины п.Существует еще "подтекст" в утверждении, что "эффективность данного алгоритма есть f(n)": время выполнения алгоритма также равно Q(/(ra)), т.е.
/(п) являетсяфункцией от га с наименьшей степенью роста, которая ограничивает сверху времявыполнения алгоритма в самом худшем случае. Но последнее условие (о наименьшейстепени роста) не является частью определения O(f(n)), часто вообще невозможносделать никакого заключения о наименьшей степени роста верхней границы.Наше определение эффективности алгоритма игнорирует константы пропорциональности, которые участвуют в определениях O(f(n)) и Q(/(n)), и для этого есть весомые причины. Во-первых, поскольку большинство алгоритмов записываются наязыках программирования высокого уровня, нам приходится описывать их в терми-нах "шагов", каждый из которых должен выполняться за конечное фиксированноевремя после трансляции их в машинный язык какого-нибудь компьютера.
Однако,как можно точно определить время выполнения какого-либо шага алгоритма, когдаоно зависит не только от "природы" самого этого шага, но также от процесса трансляции и машинных инструкций, заложенных в компьютере? Поэтому вместо точнойоценки эффективности алгоритма, пригодной только для конкретной машины (и дляполучения которой надо ещё пробраться через запутанные подробности машинныхвычислений), используют менее точные (с точностью до константы пропорциональности), но более общие оценки эффективности в терминах О(/(л)).Вторая причина, по которой используются асимптотические оценки и игнорируются константы пропорциональности, заключается в том, что асимптотическая временная сложность алгоритма в большей степени, чем эти константы, определяет граничный размер входных данных, которые можно обрабатывать посредством данногоалгоритма.
В главе 1 эта ситуация исследована подробно. С другой стороны, читательдолжен быть готовым к тому, что при анализе некоторых важных задач (например,сортировки) мы, возможно, будем применять такие утверждения, как "алгоритм Ана типовом компьютере выполняется в два раза быстрее, чем алгоритм В".Возможны ситуации, когда мы будем отходить от времени выполнения в самомхудшем случае как меры эффективности алгоритма. В частности, если известно ожидаемое распределение входных данных, на которых выполняется алгоритм, то в этойситуации среднестатистическое время выполнения алгоритма является более разумной мерой эффективности по сравнению с оценкой времени выполнения в самомхудшем случае.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
