Это вопрос из » Введения в алгоритмы » Кормена и др., Но это не домашнее задание. Вместо этого это самообучение.
Я много думал и искал в Google. Ответ, который я могу придумать:
- Используйте другой алгоритм.
- Дайте ему лучшие примеры
- Используйте лучший компьютер для запуска алгоритма
Но я не думаю, что это правильно. Изменение алгоритма — это не то же самое, что сделать алгоритм более эффективным. Также использование лучшего компьютера может увеличить скорость, но алгоритм не лучше. Это вопрос в начале книги, поэтому я думаю, что это что-то простое, что я упускаю из виду.
Итак, как мы можем изменить почти любой алгоритм, чтобы иметь хорошее время выполнения в лучшем случае?
Ответ 1
Вы можете изменить любой алгоритм, чтобы иметь наилучшую временную сложность O(n), добавив специальный случай, который, если вход соответствует этому специальному случаю, возвращает возвращаемый в кешированный жесткий код ответ (или какой-либо другой легко полученный ответ).
Например, для любого типа вы можете сделать лучший случай O(n), проверив, отсортирован ли массив, а если он есть, верните его как есть.
Обратите внимание, что это не влияет на средние или худшие случаи (при условии, что они не лучше, чем O(n)), и вы в основном улучшаете алгоритм наилучшей сложности времени.
Примечание. Если размер ввода ограничен, такая же оптимизация делает наилучший случай O(1), так как чтение ввода в этом случае равно O(1).
Ответ 2
Если бы мы могли ввести инструкцию для этого самого алгоритма в вычислительной модели самой системы, мы можем просто решить проблему в одной инструкции.
Но поскольку вы, возможно, уже обнаружили, что это очень нереалистичный подход. Таким образом, общий метод для изменения любого алгоритма, чтобы иметь наилучшее время работы, практически невозможно. То, что мы можем сделать при макс, — это применить хитрости в алгоритме общих увольнений, найденных в различных задачах.
Или вы можете пойти наивно, взяв наилучшие входные данные. Но опять же это фактически не модифицирует алгоритм. Фактически, введение алгоритма в самой вычислительной системе, а не быть крайне нереалистичным, также не является модификацией в алгоритме.
Ответ 3
Мы можем изменить алгоритм, чтобы иметь наилучшее время работы:
- Если алгоритм находится в точке его цели/решения, для ex, для возрастающего сорта, он уже сортируется по возрастанию и т.д.
- Если мы модифицируем алгоритм таким образом, что мы выводим его и выходим для его цели, то только потому, что несколько вложенных циклов будут всего одним
Ответ 4
Иногда мы можем использовать рандомизированный алгоритм, который делает случайные выборы, чтобы позволить вероятностный анализ и таким образом улучшить время выполнения.
Ответ 5
Я думаю, что единственным способом решения этой проблемы является ввод в алгоритм. Поскольку анализ случаев временной сложности зависит только от нашего ввода, насколько он сложен, сколько раз он имеет тенденцию запускать алгоритм. на основе этого анализа мы решаем, является ли наш случай лучшим, средним или худшим. Таким образом, наш вход будет определять время выполнения алгоритма в каждом случае. Или мы можем изменить наш алгоритм для улучшения во всех случаях (уменьшая сложность времени).
Вот как мы можем добиться хорошего времени выполнения в лучшем случае.
?
Log in
If this type of authorization does not work for you, convert your account using the link
-
-
September 5 2005, 21:06
Как?
Утверждение: Почти любой алгоритм можно немного изменить, радикально уменьшив время его работы в лучшем случае.
Вопрос: Как?
Спасибо.
Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы — файл n1.doc
приобрести
Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы
скачать (7725.5 kb.)
Доступные файлы (1):
- Смотрите также:
- Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: Построение и анализ, 1-е издание (Документ)
- Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: Построение и анализ, 2-е издание (Документ)
- Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: Построение и анализ (Документ)
- Хиценко В.П., Шапошникова Т.А. Практикум на ЭВМ. Алгоритмы (Документ)
- Бобцов А.А., Болтунов Г.И. и др. Управление непрерывными и дискретными процессами (Документ)
- Бобцов А.А., Болтунов Г.И. и др. Управление непрерывными и дискретными процессами (Документ)
- Саврасов Ю.С. Алгоритмы и программы в радиолокации (Документ)
- Губарени Н.М. Вычислительные методы и алгоритмы малоракурсной компьютерной томографии (Документ)
- Скиена Стивен. Алгоритмы. Руководство по разработке (Документ)
- Кристофидес Н. Теория графов. Алгоритмический подход (Документ)
- Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы (Документ)
- Лосев В.В. Микропроцессорные устройства обработки информации. Алгоритмы цифровой обработки (Документ)
n1.doc
»(» + 1)_1} Ч, 14 -«fa—1)
2
.7=2 .7=2
(см. гл. 3), получаем, что в худшем случае время работы процедуры равно
Т(га) = С1га + с2(га — 1) + с4(га — 1) + с5
га(га-1) /га(га-1)
+С7
С5 С6 С7 2
^ + ^ + ^)п
— (С2 + С4 + С5 + С8)-
Теперь функция Т(га) — квадратичная (quadratic function), т.е. имеет вид Т(га) = ага2 + 6га + с. (Константы а, Ь и с снова определяются значениями Ci-c8.)
Анализ алгоритмов 21
Время работы в худшем случае и в среднем
Итак, мы видим, что время работы в худшем случае и в лучшем случае могут сильно различаться. Большей частью нас будет интересовать время работы в худшем случае (worst-case running time), которое определяется как максимальное время работы для входов данного размера. Почему? Вот несколько причин.
- Зная время работы в худшем случае, мы можем гарантировать,
что выполнение алгоритма закончится за некоторое время, да
же не зная, какой именно вход (данного размера) попадётся. - На практике «плохие» входы (для которых время работы близ
ко к максимуму) могут часто попадаться. Например, для базы
данных плохим запросом может быть поиск отсутствующего
элемента (довольно частая ситуация). - Время работы в среднем может быть довольно близко к времени
работы в худшем случае. Пусть, например, мы сортируем слу
чайно расположенные п чисел в помощью процедуры insertion-
sort. Сколько раз придётся выполнить цикл в строках 5-8? В
среднем около половины элементов массива А[1.. j‘ — 1] болье
Aj], так что tj в среднем можно считать равным J/2, и вре
мя Т(п) квадратично зависит от п.
В некоторых случаях нас будет интересовать также среднее время работы (average-case running time, expexted running time) алгоритма на входах данной длины. Конечно, эта величина зависит от выбранного распределения вероятностей (обычно рассматривается равномерное распределение), и на практике реальное распределение входов может оказаться совсем другим. (Иногда его можно преобразовать в равномерное, используя датчик случайных чисел.)
Порядок роста
Наш анализ времени работы процедуры INSERTION-SORT был основан на нескольких упрощающих предположениях. Сначала мы предположили, что время выполнения г’-й строки постоянно и равно Cj. Затем мы огрубили оценку до an2 + Ъп + с. Сейчас мы пойдём ещё дальше и скажем, что время работы в худшем случае имеет порядок роста (rate of growth, order of growth) га2, отбрасывая члены меньших порядков (линейные) и не интересуясь коэффициентом при га2. Это записывают так: Т(га) = 0(га2) (подробное объяснение обозначений мы отложим до следующей главы).
Алгоритм с меньшим порядком роста времени работы обычно предпочтителен: если, скажем, один алгоритм имеет время работы 0(га2), а другой — 0(га3), то первый более эффективен (по крайней мере для достаточно длинных входов; будут ли реальные входы таковыми — другой вопрос).
22 Глава 1 Введение
Упражнения
1.2-1 Будем сортировать массив из п элементов так: просмотрим его и найдём минимальный элемент, который скопируем в первую ячейку другого массива. Затем просмотрим его снова и найдём следующий элемент, и так далее. Такой способ сортировки можно назвать сортировкой выбором (selection sort). Запишите этот алгоритм с помощью псевдокода. Укажите время его работы в лучшем и худшем случаях, используя ©-обозначения.
1.2-2 Вернёмся к алгоритму линейного поиска (упр. 1.1-3). Сколько сравнений потребуется в среднем этому алгоритму, если искомым элементом может быть любой элемент массива (с одинаковой вероятностью)? Каково время работы в худшем случае и в среднем? Как записать эти времена с помощью ©-обозначений?
1.2-3 Дана последовательность чисел zi, »2, . . ., хп. Покажите, что за время ©(ralogra) можно определить, есть ли в этой последовательности два одинаковых числа.
1.2-4 Даны коэффициенты uq, ai, . . . , an-i многочлена; требуется найти его значение в заданной точке х. Опишите естественный алгоритм, требующий времени 0(га2). Как выполнить вычисления за время 0(га), не используя дополнительного массива? Используйте «схему Горнера»:
тг-1
i=o
1.2-5 Как записать выражение га3/1000 — 100га2 — 100га + 3 с помощью ©-обозначений?
1.2-6 Почти любой алгоритм можно немного изменить, радикально уменьшив время его работы в лучшем случае. Как?
1.3. Построение алгоритмов
Есть много стандартных приёмов, используемых при построении алгоритмов. Сортировка вставками является примером алгоритма, действующего по шагам (incremental approach): мы добавляем элементы один за другим к отсортированной части массива.
В этом разделе мы покажем в действии другой подход, который называют «разделяй и властвуй» (divide-and-conquer approach), и построим с его помощью значительно более быстрый алгоритм сортировки.
Построение алгоритмов 23
1.3.1. Принцип «разделяй и властвуй»
Многие алгоритмы по природе рекурсивны (recursive algorithms): решая некоторую задачу, они вызывают самих себя для решения её подзадач. Идея метода «разделяй и властвуй» состоит как раз в этом. Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются (с помощью рекурсивного вызова— или непосредственно, если размер достаточно мал). Наконец, их решения комбинируются и получается решение исходной задачи.
Для задачи сортировки эти три этапа выглядят так. Сначала мы разбиваем массив на две половины меньшего размера. Затем мы сортируем каждую из половин отдельно. После этого нам остаётся соединить два упорядоченных массива половинного размера в один. Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не дойдёт до единицы (любой массив длины 1 можно считать упорядоченным).
Нетривиальной частью является соединение двух упорядоченных массивов в один. Оно выполняется с помощью вспомогательной процедуры merge (А, р, д, г). Параметрами этой процедуры являются массив А и числа р, д, г, указывающие границы сливаемых участков. Процедура предполагает, что р ^ q < г и что участки Ар. .q] и A[q + 1. .г] уже отсортированы, и сливает (merges) их в один участок Ар. .г].
Мы оставляем подробную разработку этой процедуры читателю (упр. 1.3-2), но довольно ясно, что время работы процедуры merge есть 0(га), где п — общая длина сливаемых участков (п = г—р+1). Это легко объяснить на картах. Пусть мы имеем две стопки карт, и в каждой карты идут сверху вниз в возрастающем порядке. Как сделать из них одну? На каждом шаге мы берём меньшую из двух верхних карт и кладём её (рубашкой вверх) в результирующую стопку. Когда одна из исходных стопок становится пустой, мы добавляем все оставшиеся карты второй стопки к результирующей стопке. Ясно, что каждый шаг требует ограниченного числа действий, и общее число действий есть 0(га).
Теперь напишем процедуру сортировки слиянием MERGE-SoRT(A,p, r), которая сортирует участок Л[р..г] массива А, не меняя остальную часть массива. При р ^ г участок содержит максимум один элемент, и тем самым уже отсортирован. В противном случае мы отыскиваем число д, которое делит участок на две примерно равные части Л[р..д] (содержит [га/2] элементов) и Л[д+1..г] (содержит п/1 элементов). Здесь через х мы обозначаем целую часть х (наибольшее целое число, меньшее или равное ж), а через х — наименьшее целое число, большее или равное х.
24 Глава 1 Введение
sorted sequence — отсортированная последовательность
merge — слияние
initial sequence — начальная последовательность
Рис. 1.3 Сортировка слиянием для массива А = (5, 2, 4, 6, 1, 3, 2, 6).
MERGE-SORT (А, р, г)
1 if р < г
2 then д<- [(р + г)/2
- merge-sort(a,p, </)
- merge-sort(a,</ + l,r)
- merge (A, p, g, r)
Весь массив теперь можно отсортировать с помощью вызова merge-sort(a, I, length[A]). Если длина массива п = length[A] есть степень двойки, то в процессе сортировки произойдёт слияние пар элементов в отсортированные участки длины 2, затем слияние пар таких участков в отсортированные участки длины 4 и так далее до п (на последнем шаге соединяются два отсортированных участка длины га/2). Этот процесс показан на рис. 1.3.
1.3.2. Анализ алгоритмов типа «разделяй и властвуй»
Как оценить время работы рекурсивного алгоритма? При подсчёте мы должны учесть время, затрачиваемое на рекурсивные вызовы, так что получается некоторое рекуррентное соотношение (recurrence equation). Далее следует оценить время работы, исходя из этого соотношения.
Вот примерно как это делается. Предположим, что алгоритм разбивает задачу размера га на а подзадач, каждая из которых имеет в Ъ раз меньший размер. Будем считать, что разбиение требует времени -D(ra), а соединение полученных решений — времени С(п).
Построение алгоритмов 25
Тогда получаем соотношение для времени работы Т (га) на задачах размера га (в худшем случае): Т(га) = аТ(п/Ъ) + D(n) + C(n). Это соотношение выполнено для достаточно больших га, когда задачу имеет смысл разбивать на подзадачи. Для малых га, когда такое разбиение невозможно или не нужно, применяется какой-то прямой метод решения задачи. Поскольку га ограничено, время работы тоже не превосходит некоторой константы.
Анализ сортировки слиянием
Для простоты будем предполагать, что размер массива (га) есть степень двойки. (Как мы увидим в главе 4, это не очень существенно.) Тогда на каждом шаге сортируемый участок делится на две равные половины. Разбиение на части (вычисление границы) требует времени 0(1), а слияние — времени 0(га). Получаем соотношение
ТЫ = ‘ если п = j
| 2Т(га/2) + 0(га/2), если га > 1.
Как мы увидим в главе 4, это соотношение влечёт Т(га) = ©(ralogra), где через log мы обозначаем двоичный логарифм (основание логарифмов, впрочем, не играет роли, так как приводит лишь к изменению константы). Поэтому для больших га сортировка слиянием эффективнее сортировки вставками, требующей времени 0(га2).
Упражнения
1.3-1 Следуя образцу рис. 1.3, показать работу сортировки слиянием для массива А = (3, 41, 52, 26, 38, 57, 9, 49).
1.3-2 Написать текст процедуры merge (А, р, д, г). 1.3-3 Докажите по индукции, что если
ты = I 2‘ если п = 2‘
П‘ ~ | 2Т(га/2) + га, если га = 1k и k > 1,
то Т(га) = ralogra (при всех га, являющихся степенями двойки).
1.3-4 Сортировку вставками можно оформить как рекурсивную процедуру: желая отсортировать А[1 . .га], мы (рекурсивно) сортируем А[1 . .га — 1], а затем ставим А[п] на правильное место в отсортированном массиве А[1 . .га — 1]. Напишите рекуррентное соотношение для времени работы такой процедуры.
26 Глава 1 Введение
1.3-5 Возвращаясь к задаче поиска (упр. 1.1-3), заметим, что при поиске в отсортированном массиве мы можем сначала сравнить искомый элемент со средним элементом массива, узнать, в какой половине его следует искать, а затем применить ту же идею рекурсивно. Такой способ называется двоичным поиском (binary search). Напишите соответствующую программу, используя цикл или рекурсию. Объясните, почему время её работы есть ©(logга).
1.3-6 Заметим, что цикл while в строках 5-7 процедуры INSERTION-SORT (разд. 1.1) просматривает элементы отсортированного участка А[1. .j — 1] подряд. Вместо этого можно было бы использовать двоичный поиск (упр. 1.3-5), чтобы найти место вставки за время ©(logга). Удастся ли таким образом сделать общее время работы равным 0(га log га)?
1.3-7* Дан массив S из га действительных чисел, а также число х. Как за время ©(ralogra) определить, можно ли представить х в виде суммы двух элементов массива 5?
Замечания
Как мог бы сказать Козьма Прутков, хороший алгоритм подобен острому ножу — тот и другой достигают цели легко и просто. Другое сравнение: человек, пользующийся плохим алгоритмом, подобен повару, отбивающему мясо отвёрткой: едва съедобный и малопривлекательный результат достигается ценой больших усилий.
Часто разница между плохим и хорошим алгоритмом более существенна, чем между быстрым и медленным компьютером. Пусть мы хотим отсортировать массив из миллиона чисел. Что быстрее — сортировать его вставками на суперкомпьютере (100 миллионов операций в секунду) или слиянием на домашнем компьютере (1 миллион операций)? Пусть к тому же сортировка вставками написана на ассемблере чрезвычайно экономно, и для сортировки га чисел нужно, скажем, лишь 2га2 операций. В то же время алгоритм слиянием написан без особой заботы об эффективности и число операций есть 50га log га. Для сортировки миллиона чисел получаем
2 • (106)2 операций
= 20 000 секунд и 5,56 часов
10 операций в секунду для суперкомпьютера и всего
50 • (106) log(106) операций
1 000 секунд к, 17 минут
106 операций в секунду для домашнего компьютера.
Мы видим, что разработка эффективных алгоритмов — не менее важная компьютерная технология, чем разработка быстрой электроники. В этой области также происходит заметный прогресс.
Задачи к главе 1
27
Задачи
»(» + 1)
Федеральное агентство по образованию
Глазовский инженерно-экономический институт (филиал) государственного образовательного учреждения высшего профессионального образования «Ижевский государственный технический университет»
Д.А. Негодин
Алгоритмы сортировки и порядковые статистики
Лекции по курсу «Алгоритмизация и прикладное программирование»
Глазов 2006
1
ББК 22.12 Н41
Негодин, Д.А. Алгоритмы сортировки и порядковые статистики: Лекции по курсу «Алгоритмизация и прикладное программирование» / Д.А. Негодин. — Глазов: Издательство Глазовского инженерно-экономического института, 2006. — 36 с.
Рецензент: к.п.н. Ю.В. Иванов, доцент кафедры дидактики физики и информационных технологий Глазовского государственного педагогического института им. В.Г. Короленко.
Курс лекций посвящен рассмотрению различных алгоритмов сортировки массивов и вычисления порядковых статистик. Кроме теоретического материала приведены примеры программной реализации алгоритмов, а также общие принципы исследования алгоритмов. Разработаны лабораторные работы по изучаемому курсу.
Предназначено для студентов дневного и вечернего отделений вузов.
Дмитрий Алексеевич Негодин
Алгоритмы сортировки и порядковые статистики
Лекции по курсу «Алгоритмизация и прикладное программирование»
© Д.А. Негодин, 2006 © ГИЭИ (филиал) ГОУ ВПО ИжГТУ, 2006
2
Введение. Основные понятия
Введение. Основные понятия
Информация — основное неопределяемое понятие.
Алгоритм — это формально описанная вычислительная процедура, получающая исходные данные, называемые также входом алгоритма или его аргументом, и выдающая результат вычислений на выход.
Программирование — теоретическая и практическая деятельность, связанная с созданием программы.
Прикладная программа — программа, предназначенная для решения задачи или класса задач в определенной области применения систем обработки информации.
Алгоритм строится для решения тех или иных задач. Формулировка задачи описывает, каким требованиям должно удовлетворять решение задачи, а алгоритм, решающий эту задачу, находит объект, этим требованиям удовлетворяющий.
Алгоритм считается правильным, если на любом допустимом для данной задачи входе он заканчивает работу и выдает результат, удовлетворяющий требованиям задачи. В этом случае говорят, что алгоритм решает поставленную задачу. Неправильный алгоритм может дать для некоторого входа неверный результат или вовсе не остановиться. В редких случаях неправильный алгоритм может быть полезен, если ошибки достаточно редки.
Алгоритм может быть написан на естественном языке, языке программирования, в машинных кодах, в виде блок-схемы, важно только, чтобы процедура действий была строго описана.
Алгоритм обладает основными свойствами:
•Дискретность — разбиение процесса обработки информации на более простые этапы (шаги выполнения), выполнение которых не вызывает затруднений.
•Определенность — однозначность выполнения каждого отдельного шага преобразования информации.
•Выполнимость — конечность действий алгоритма решения задачи, позволяющая получить желаемый результат при допустимых исходных данных за конечное число шагов.
•Массовость — пригодность алгоритма для решения определенного класса задач. Алгоритмизация — этап решения задачи, состоящий в нахождении по форму-
лировке задачи алгоритма ее решения.
Алгоритмизация — раздел информатики, изучающий методы, приемы построения алгоритмов и их свойства (иногда также называют алгоритмикой).
Для записи алгоритмов могут быть использованы псевдокод или блок-схемы.
3
Алгоритм сортировки вставками
Алгоритм сортировки вставками
Алгоритм удобен для сортировки коротких последовательностей. Примером может являться вставка очередной карты в группу уже упорядоченных карт. При этом вставка каждого нового элемента приводит к смещению всех последующих элементов в сторону больших индексов.
Входным параметром алгоритма является массив a[1..N ], подлежащий сорти-
ровке. Представим алгоритм в виде процедуры Insertion_Sort. Последовательность сортируется на месте, без использования дополнительной памяти, помимо массива используется только фиксированное число ячеек памяти. По окончании выполнения процедуры массив должен быть упорядочен по возрастанию.
Рассмотрим действие алгоритма на следующем примере.
Рисунок 1 — Пример сортировки методом вставки
Первоначально массив, состоящий из шести элементов, был неупорядоченным — строка 1 на рисунке 1. Считаем, что массив (подмассив) состоящий из одного элемента, является упорядоченным, значит первое число, образующее подмассив из одного элемента, является упорядоченным и начинаем рассмотрение со второго числа. Второе число, равное двум, необходимо переставить в упорядоченную часть массива так чтобы порядок в ней не изменился. Значит, число два перемещается на первое место, а все остальные элементы упорядоченной части сдвигаются на одну позицию вправо — строка 2 на рисунке 1.
Следующее, третье число, равное четырем, также следует переместить в упорядоченную часть. Оно расположится между числами два и пять. Все числа, которые располагаются правее места вставки, смещаются вправо на одну позицию — строка 3 на рисунке 1.
Четвертое число, равное 6, также переносим в упорядоченную часть массива, его необходимо вставить в крайнюю правую позицию, и фактически оно останется на своем месте — строка 4 на рисунке 1.
Все последующие числа переставляются аналогично, и по окончании перестановок будет получен упорядоченный массив — строка 6 на рисунке 1.
Программу, реализующую данный алгоритм, можно представить следующим образом:
Insertion_Sort
1For j:=2 to Length(a) do
2Key:=a[j]
3i:=j-1
4While i>0 and a[i]>key do
5a[i+1]:=a[i]
6i:=i-1
7a[i+1]:=key
Алгоритм сортировки вставками
Рассмотрим работу программы. Первая строка определят цикл, позволяющий рассматривать все элементы, начиная со второго. Переменная j является индексом
перемещаемого элемента.
Во второй строке происходит запоминание в переменной key значения пере-
мещаемого числа.
В третьей строке вычисляем индекс последнего элемента, входящего в упорядоченную часть подмассива.
Строки 4, 5 и 6 представляют собой цикл перемещения чисел. Если число a[i] больше перемещаемого числа key , то независимо от позиции, в которую будет вставлено число key , число a[i] следует переместить на одну позицию вправо. Поэтому цикл организован следующим образом: пока a[i]> key и не достигнуто нача-
ло массива каждое число перемещается на одну позицию вправо. При первой итерации число, расположенное слева от числа key , занимает его место, на место пере-
ставленного числа сдвигается следующее и так далее. После того как будет достигнута позиция, для которой условие a[i]> key невыполнимо, в эту позицию и запи-
шется число key — строка 7 программы.
Если условие a[i]> key будет выполняться для всех чисел, то число key будет записано в первую ячейку.
Анализ алгоритма
Рассматривая различные алгоритмы решения одной и той же задачи, следует анализировать, сколько вычислительных ресурсов они требуют (время работы, память), и выбрать наиболее эффективный. В качестве модели компьютера будем использовать обыкновенную однопроцессорную машину с произвольным доступом к памяти, не предусматривающую параллельного исполнения операций.
Проведем анализ алгоритма сортировки вставками.
Время сортировки вставками зависит от размера массива: чем больше массив, тем дольше идет сортировка. Кроме этого, в данном случае на время сортировки влияет еще и степень сортировки элементов в первоначальном массиве.
Одной из характеристик алгоритма является размер входа, то есть количество данных, используемых при работе.
Временем работы алгоритма называется число элементарных шагов, которые он выполняет. Будем считать, что одна строка псевдокода требует не более чем фиксированного числа операций.
Рассмотрим время работы алгоритма Insertion_Sort. Обозначим через N размер массива.
|
Псевдокод |
Стоимость |
Число повторений |
|
|
For j:=2 to N do |
C1 |
N , от 2 до N и еще 1 действие при проверке |
|
|
N +1–го значения |
|||
|
Key:=a[j] |
C2 |
N −1, по сравнению с предыдущей строкой, |
|
|
при N +1 команда не выполняется. |
|||
|
i:=j-1 |
C3 |
N −1, аналогично предыдущей строке. |
5
Алгоритм сортировки вставками
|
Псевдокод |
Стоимость |
Число повторений |
|
|
N |
|||
|
∑t j , условие проверяется в цикле от 2 до ко- |
|||
|
While i>0 and |
C4 |
j=2 |
|
|
личества элементов массива, при каждой ите- |
|||
|
a[i]>key do |
|||
|
рации число проверок t j различное, зависящее |
|||
|
от степени упорядоченности массива. |
|||
|
N |
|||
|
∑(t j −1), число повторений операций меньше |
|||
|
a[i+1]:=a[i] |
C5 |
j=2 |
|
|
на 1 при каждой итерации, так как при невы- |
|||
|
полнении условия проверка выполняется, а |
|||
|
команды нет. |
|||
|
i:=i-1 |
N |
||
|
C6 |
∑(t j −1), аналогично предыдущей строке. |
||
|
j=2 |
|||
|
a[i+1]:=key |
C7 |
N −1, количество повторений в цикле. |
Просуммируем вклады всех строк и получим время выполнения алгоритма:
T (N ) =C1N +C2 (N −1)+C3 (N −1)+
|
N |
N |
n |
(1.1) |
|
|
+C4 ∑t j +C5 ∑(t j −1)+C6 ∑(t j −1)+C7 (N −1). |
||||
|
j=2 |
j=2 |
j=2 |
Рассмотрим наиболее благоприятный и неблагоприятный случаи выполнения алгоритма. Минимальное время будет получено, если массив на входе алгоритма
|
будет упорядочен, в этом случае t j |
=1 и общее время будет равно |
|
|
T (N,t j =1)=C1N +C2 (N −1) |
+C3 (N −1)+C4 (N −1)+C7 |
(N −1)= |
|
= N (C1 +C2 +C3 +C4 +C7 )+(C2 +C3 +C4 +C7 ). |
(1.2) |
|
|
Значит, в наиболее благоприятном случае время выполнения алгоритма явля- |
||
|
ется линейной функцией от числа элементов в массиве: |
||
|
T (N,t j |
=1)= AN + B , |
(1.3) |
где константы определяются в зависимости от выбранных коэффициентов.
Теперь определим время выполнения алгоритма в наиболее неблагоприятном случае, когда массив упорядочен не по возрастанию, а по убыванию, то есть каждый элемент следует переставить на максимальное расстояние. Каждый элемент a[j] нужно будет сравнивать со всеми элементами a[1]…a[j-1], тогда t j = j . В этом
случае суммы можно записать следующим образом:
|
N |
N |
2 |
+ N |
N |
2 |
− N |
|||||||
|
∑j = |
−1, |
∑( j −1)= |
N |
, |
(1.4) |
||||||||
|
2 |
2 |
||||||||||||
|
j=2 |
j=2 |
||||||||||||
|
что получается из рассмотрения свойств арифметической прогрессии. |
|||||||||||||
|
Формула суммы |
N |
первых членов |
арифметической |
прогрессии |
|||||||||
|
SN |
= |
a1 + aN |
N . |
||||||||||
|
2 |
6
Алгоритм сортировки вставками
N
Ряд ∑j = 2 +3 + 4 +…+ N является суммой первых членов арифметической
j=2
|
прогрессии, первый член равен a0 = 2 , последний член равен aN = N , а всего членов |
||||||||||||||||||||||||
|
(N −1), разность прогрессии d =1, тогда сумма первых членов |
||||||||||||||||||||||||
|
S = |
2 + N |
(N −1)= |
N 2 |
+ N |
−1. |
(1.5) |
||||||||||||||||||
|
2 |
2 |
|||||||||||||||||||||||
|
Второй ряд |
(N −1)=1+(N −1)(N −1)= N |
2 |
− N . |
(1.6) |
||||||||||||||||||||
|
∑( j −1)=1+ 2 +3 +…+ |
||||||||||||||||||||||||
|
N |
||||||||||||||||||||||||
|
j=2 |
2 |
2 |
||||||||||||||||||||||
|
Значит, в худшем случае время исполнения алгоритма будет равно |
||||||||||||||||||||||||
|
T (N,t j = j)=C1N +C2 (N −1)+C3 (N −1) |
N |
2 |
+ N |
|||||||||||||||||||||
|
+C4 |
−1 + |
|||||||||||||||||||||||
|
2 |
||||||||||||||||||||||||
|
+(C5 +C6 ) |
N 2 − N |
+C7 (N −1)= |
(1.7) |
|||||||||||||||||||||
|
N 2 |
2 |
C |
−C −C |
|||||||||||||||||||||
|
4 |
6 |
|||||||||||||||||||||||
|
= |
(C4 +C5 +C6 )+ N C1 |
+C2 +C3 + |
5 |
+C7 |
− |
(C2 +C3 +C4 +C7 ) |
||||||||||||||||||
|
2 |
||||||||||||||||||||||||
|
2 |
||||||||||||||||||||||||
|
Из (1.7) следует, что зависимость времени исполнения от количества элемен- |
||||||||||||||||||||||||
|
тов в неблагоприятном случае является квадратичной: |
||||||||||||||||||||||||
|
T (N,t j = j)= AN 2 + BN +C , |
(1.8) |
константы A, B, C выбираются в зависимости от коэффициентов Ci .
Из расчетов видно, что продолжительность работы алгоритма в лучшем и в худшем случаях может различаться значительно. Это наиболее сильно будет проявляться при большом количестве элементов массива. Для алгоритма наиболее важным является время работы в худшем случае, которое определяется как максимальное время работы для входов данного размера:
1.Зная время работы в худшем случае, мы можем гарантировать, что выполнение алгоритма закончится за некоторое время, даже не зная, какой именно вход данного размера попадется.
2.На практике «плохие» входы попадаются довольно часто.
3.Время работы в среднем может быть довольно близко ко времени работы в худшем случае.
При работе с алгоритмом принято характеризовать его, кроме наибольшего и наименьшего, еще и средним временем. Среднее время выполнения алгоритма представляет собой усредненное значение результатов работы при всех возможных комбинациях входов или при достаточно большом их количестве, полученных случайным образом.
Порядком роста времени выполнения называется максимальная степень переменной в функции T (N ) в худшем случае работы алгоритма. Так, в рассмотренном
случае максимальная степень равна двум, это записывается так T (N )= Θ(N 2 ). Наиболее предпочтительным является алгоритм с минимальным порядком роста.
7
Алгоритм сортировки вставками
Упражнения
1.Измените процедуру Insertion_Sort так, чтобы она сортировала числа в невозрастающем порядке.
2.Напишите процедуру линейного поиска (Linear_Search), которая просматривает массив a в поисках элемента, равного V. Определите, сколько потребуется сравнений в среднем этому алгоритму. Каково время работы в лучшем, худшем и среднем случаях? Запишите эти времена с помощью Θ-обозначений.
3.Напишите процедуру сортировки выбором (Selection_Sort). Сортировка осуществляется следующим образом: весь массив просматривается и выбирается минимальный элемент, он извлекается и помещается в первую ячейку другого массива, затем определяется следующий минимальный из оставшихся и так далее. Укажите время его работы в лучшем и худшем случаях, используя Θ— обозначения.
4.Дана последовательность чисел {xi}, i =1, N . Покажите, что за время Θ(N ln N )
можно определить, есть ли в этой последовательности два одинаковых числа.
5.Даны коэффициенты {ai}, i = 0,(N −1) многочлена. Требуется найти его значение
взаданной точке x . Опишите естественный алгоритм, требующий времени
Θ(N 2 ). Как выполнить вычисления за время Θ(N ), не используя дополнитель-
ный массив? Используйте «схему Горнера»:
N −1
∑ai xi =(…(aN −1x + aN −2 )x +…+ a1 )x + a0 .
i=0
6.Почти любой алгоритм можно немного изменить, радикально уменьшив скорость его работы в лучшем случае. Как?
Задачи
1.Пусть имеется алгоритм, решающий задачу размера N за f (N ) микросекунд.
Каков максимальный размер задачи, которую он сможет решить за время t ? Найти его для всех функций и времен, перечисленных в таблице.
|
1 с |
1 мин |
1 час |
1 день 1 месяц |
1 год |
1 век |
ln N
N
N
N ln N
N 2
N 3
2N
N !
8
Алгоритм сортировки слиянием
Алгоритм сортировки слиянием
Алгоритм сортировки вставкой является «пошаговым алгоритмом», который является одним из наиболее медленных.
Рассмотрим алгоритм, построенный по принципу «Разделяй и властвуй».
В основе этого принципа лежит использование рекурсивных функций: решая некоторую задачу, они вызывают самих себя для решения ее подзадач. Задача разбивается на несколько подзадач меньшего размера. Затем подзадачи решаются с помощью рекурсивного вызова или непосредственно, если размер достаточно мал.
Для задачи сортировки эти три этапа выглядят так. Сначала разбивается массив на две половинки меньшего размера, затем сортируется каждая половинка в отдельности, после этого остается соединить два упорядоченных массива половинного размера в один. Рекурсивное разбиение массива происходит до тех пор, пока размер массива не дойдет до единицы, при этом любой массив длины 1 можно считать упорядоченным.
Слияние упорядоченных рядов будем производить при помощи вспомогательной процедуры Merge(a,p,q,r). Параметрами процедуры являются a — массив данных, p , q , r — индексы массива, причем p ≤ q ≤ r и участки a[p..q], a[q +1,r]
уже отсортированы.
Рассмотрим рекуррентную процедуру сортировки Merge_Sort(a,p,r), которая сортирует участок a[p..r] массива, не изменяя остальную часть массива. Если p = r , то последовательность содержит один элемент и, значит, уже отсортирована. В случае, если p > r , следует найти число q , которое делит последовательность на
две примерно равные части.
Тогда искомая процедура будет иметь вид
Merge_Sort(a,p,r);
1if p<r then
2q:=int[(p+q)/2]
3Merge_Sort(a,p,q)
4Merge_Sort(a,q+1,r)
5Merge(a,p,q,r)
|
Исходная |
последова- |
||
|
тельность разбивается на |
|||
|
две части, каждая часть сор- |
|||
|
тируется отдельно, а затем |
|||
|
части соединяются — рису- |
|||
|
нок 2. Для сортировки каж- |
|||
|
дой части последовательно- |
Рисунок 2 — Пример сортировки методом слияния |
||
|
сти процедура |
рекуррентно |
||
вызывает сама себя. Тогда для сортировки всего массива необходимо вызвать процедуру Merge_Sort(a,1,N). Если длина массива является степенью двух, то в процессе сортировки произойдет слияние пар таких участков в отсортированные участки длины 2, затем 4, 8, 16 и так далее, на последнем этапе будут сливаться последовательности длиной N
2 .
9
Алгоритм сортировки слиянием
Рассмотрим алгоритм процедуры Merge(a,p,q,r).
Merge(a,p,q,r)
1k:=p; m:=q+1; i:=1;
2while i<=r-p+1
3if (k<q+1) and (m<r+1)
4then if a[k]>a[m]
|
5 |
then b[i]:=a[m]; inc(m); |
|
6 |
else b[i]:=a[k]; inc(k); |
|
7 |
inc(i) |
|
8 |
else if k=q |
|
9 |
then while m<=r do |
|
10 |
a[i]:=a[m]; inc(m); inc(i) |
|
11 |
else while k<=q do |
|
12 |
B[i]:=a[k]; inc(k); inc(i) |
13for i:=1 to r-p+1 do
14a[p+i-1]:=b[i]
Части массива уже упорядочены, поэтому для соединения подчастей в один массив из каждой части выбираются минимальные элементы a[k] — из первой час-
ти массива и a[m] — из второй части, из них выбирается минимальный и помеща-
ется в массив b . Так продолжается до тех пор, пока не будут перенесены все элементы. Если одна из частей заканчивается, то вторая просто перемещается в массив b .
Анализ алгоритма
Очевидно, что время исполнения процедуры пропорционально числу элементов, то есть T (n) = Θ(n) . Существенным недостатком процедуры является то, что
она должна резервировать дополнительную память под временный массив b , который удаляется после окончания работы процедуры.
Проанализируем работу рекурсивной процедуры.
При оценке времени работы следует учесть время, затрачиваемое на рекурсивные вызовы процедур. То есть получается некоторое рекуррентное соотношение, исходя из которого следует оценить время работы.
Предположим, что алгоритм разбивает задачу размера N на A подзадач, каждая из которых имеет в B раз меньший размер. Будем считать, что на разбивку требуется время D(N ) , а соединение происходит за время C(N ) . Тогда получаем соот-
ношение для худшего времени работы в виде
|
T (N )= AT |
N |
+ D(N )+C (N ). |
(2.1) |
||
|
B |
|||||
Это соотношение выполнимо для достаточно больших N .
Для простоты будем считать, что размер массива есть степень двойки (хотя в общем случае это несущественно). Тогда на каждом этапе сортировки участок делится на две равные половины. Разбиение на части отрезка требует времени Θ(1)
(определяются границы и ищется середина, то есть от числа элементов ничего не зависит). Слияние требует времени Θ(N ), тогда время выполнения определяется вы-
ражением
10
Соседние файлы в папке МС
- #
22.03.20165.51 Кб3Unit1.pas
- #
- #
- #
- #
- #
- #
This is a question from Introduction to Algorithms by Cormen et al, but this isn’t a homework problem. Instead, it’s self-study.
I have thought a lot and searched on Google. The answer that I can think of are:
- Use another algorithm.
- Give it best-case inputs
- Use a better computer to run the algorithm
But I don’t think these are correct. Changing the algorithm isn’t the same as making an algorithm have better performance. Also using a better computer may increase the speed but the algorithm isn’t better. This is a question in the beginning of the book so I think this is something simple that I am overlooking.
So how can we modify almost any algorithm to have a good best-case running time?
bruno
2,2151 gold badge19 silver badges31 bronze badges
asked Aug 7, 2013 at 12:46
Aseem BansalAseem Bansal
6,65213 gold badges45 silver badges84 bronze badges
5
You can modify any algorithm to have a best case time complexity of O(n) by adding a special case, that if the input matches this special case — return a cached hard coded answer (or some other easily obtained answer).
For example, for any sort, you can make best case O(n) by checking if the array is already sorted — and if it is, return it as it is.
Note it does not impact average or worst cases (assuming they are not better then O(n)), and you basically improve the algorithm’s best case time complexity.
Note: If the size of the input is bounded, the same optimization makes the best case O(1), because reading the input in this case is O(1).
answered Aug 7, 2013 at 12:50
5
If we could introduce an instruction for that very algorithm in the computation model of the system itself, we can just solve the problem in one instruction.
But as you might have already discovered that it is a highly unrealistic approach. Thus a generic method to modify any algorithm to have a best case running time is next to impossible. What we can do at max is to apply tweaks in the algorithm for general redundancies found in various problems.
Or you can go naive by taking the best case inputs. But again that isn’t actually modifying the algorithm. In fact, introducing the algorithm in the computation system itself, instead of being highly unrealistic, isn’t a modification in the algorithm either.
answered Jul 23, 2015 at 7:20
Vikas PrasadVikas Prasad
3,0814 gold badges28 silver badges39 bronze badges
The ways we can modify the algorithm to have a best case running time are:
- If the algorithm is at the point of its purpose/solution , For ex, for an increasing sort , it is already ascending order sorted and so on .
- If we modify the algorithm such that we output and exit for its purpose only hence forcing multiple nested loops to be just one
answered Jun 16, 2017 at 14:53
We can sometimes use a randomized algorithm, that makes random choices, to allow a probabilistic analysis and thus improve the running time..
answered Sep 2, 2018 at 22:13
1
I think the only way for this problem is the input to the algorithm. Because the cases in time complexity analysis only depend on our input, how complex it is, how much times it tends to run the algorithm. on this analysis, we decide whether our case is best, average or worst.
So, our input will decide the running time for an algorithm in every case.
Or we can change our algorithm to improve for all cases(reducing the time complexity).
These are the ways we can achieve good best-case running time.
answered Jul 3, 2019 at 7:39
We can modify an algorithm for some special-case conditions, so if the input satisfies that condition, we can output the pre-computed answer. Generally, the best case running time is not a good measure for an algorithm. We need to know how the algorithm performes in worst case.
answered Mar 26, 2021 at 6:53
i just reached to this discussion while looking for an answer. what i think there is only one way to make any algorithm best case by having it a fixed input instead of varing input. if we have an fixed input always the cost and time complexity will always be O(1)
answered Apr 3, 2021 at 16:01
Это вопрос из Введение в алгоритмы Кормен и др., но это не домашнее задание. Вместо этого это самообучение.
Я много думал и искал в Google. Ответ, который я могу придумать, таков:
- Используйте другой алгоритм.
- Дайте ему наилучшие данные
- Используйте лучший компьютер для запуска алгоритма
Но я не думаю, что это правильно. Изменение алгоритма — это не то же самое, что повышение производительности алгоритма. Также использование более качественного компьютера может увеличить скорость, но алгоритм не лучше. Это вопрос в начале книги, поэтому я думаю, что это что-то простое, что я упускаю из виду.
Итак, как мы можем изменить практически любой алгоритм, чтобы обеспечить оптимальное время работы?
7 ответов
Лучший ответ
Вы можете изменить любой алгоритм, чтобы получить временную сложность в лучшем случае O(n), добавив особый случай: если входные данные соответствуют этому особому случаю — возвращать кэшированный жестко закодированный ответ (или какой-либо другой легко получаемый ответ).
Например, для любой сортировки в лучшем случае можно O(n) проверить, отсортирован ли уже массив, и, если да, вернуть его как есть.
Обратите внимание, что это не влияет на средние или наихудшие случаи (при условии, что они не лучше, чем O(n)), и вы в основном улучшаете временную сложность алгоритма для наилучшего случая.
Примечание. Если размер входных данных ограничен, та же оптимизация дает наилучший вариант O(1), потому что чтение входных данных в этом случае равно O(1).
52
amit
7 Авг 2013 в 21:50
Способы изменения алгоритма для достижения наилучшего времени работы:
- Если алгоритм находится в точке своей цели / решения, например, для возрастающей сортировки, он уже отсортирован в возрастающем порядке и так далее.
- Если мы изменим алгоритм таким образом, что мы будем выводить и выходим только по его назначению, следовательно, заставляем несколько вложенных циклов быть только одним
1
Sandeep Anand
16 Июн 2017 в 17:53
Иногда мы можем использовать рандомизированный алгоритм, который делает случайный выбор, чтобы обеспечить вероятностный анализ и, таким образом, сократить время выполнения.
0
Aniket Mukherjee
3 Сен 2018 в 01:13
Я думаю, что единственный способ решить эту проблему — это ввести в алгоритм. Поскольку случаи в анализе временной сложности зависят только от наших входных данных, насколько они сложны и сколько раз он имеет тенденцию запускать алгоритм. на основе этого анализа мы решаем, является ли наш случай лучшим, средним или худшим. Итак, наш ввод будет определять время работы алгоритма в каждом случае. Или мы можем изменить наш алгоритм, чтобы улучшить его для всех случаев (уменьшив временную сложность).
Это способы достижения оптимального времени работы.
0
Viraj sharma
3 Июл 2019 в 10:39
Мы можем изменить алгоритм для некоторых особых условий, поэтому, если входные данные удовлетворяют этому условию, мы можем вывести предварительно вычисленный ответ. Как правило, время работы в лучшем случае не является хорошим показателем для алгоритма. Нам нужно знать, как алгоритм работает в худшем случае.
0
Akshat Divya
26 Мар 2021 в 09:53
Я просто дошел до этого обсуждения, пока искал ответ. что я думаю, есть только один способ сделать любой алгоритм наилучшим, используя фиксированный ввод вместо изменяющегося ввода. если у нас есть фиксированный вход, всегда стоимость и временная сложность всегда будет O (1)
0
Muhammad Mubeen
3 Апр 2021 в 19:01
Если бы мы могли ввести инструкцию для этого самого алгоритма в вычислительную модель самой системы, мы могли бы просто решить проблему за одну инструкцию.
Но, как вы уже могли заметить, это крайне нереалистичный подход. Таким образом, универсальный метод модификации любого алгоритма для достижения наилучшего времени работы практически невозможен. Что мы можем сделать на max, так это применить настройки в алгоритме для общих избыточностей, обнаруженных в различных проблемах.
Или вы можете пойти наивно, выбрав лучший вариант. Но опять же, это на самом деле не меняет алгоритм. Фактически, введение алгоритма в саму вычислительную систему, вместо того, чтобы быть крайне нереалистичным, также не является модификацией алгоритма.
5
Vikas Prasad
23 Июл 2015 в 10:20
