Время работы в худшем случае и в среднем

Итак, мы видим, что время работы в худшем случае и в лучшем случае могут сильно различаться. Большей частью нас будет интересовать время работы в худшем случае (worst-case running time), которое определяется как максимальное время работы для входов данного размера. Почему? Вот несколько причин.

•Зная время работы в худшем случае, мы можем гарантировать, что выполнение алгоритма закончится за некоторое время, даже не зная, какой именно вход (данного размера) попадётся.

•На практике «плохие» входы (для которых время работы близко к максимуму) могут часто попадаться. Например, для базы данных плохим запросом может быть поиск отсутствующего элемента (довольно частая ситуация).

•Время работы в среднем может быть довольно близко к времени работы в худшем случае. Пусть, например, мы сортируем случайно расположенные га чисел в помощью процедуры Insertion-Sort. Сколько раз придётся выполнить цикл в строках 5-8? В среднем около половины элементов массива А[1.. j - 1] болье A[j], так что tj в среднем можно считать равным j/2, и время Т(п) квадратично зависит от га.

В некоторых случаях нас будет интересовать также среднее время работы (average-case running time, expexted running time) алгоритма на входах данной длины. Конечно, эта величина зависит от выбранного распределения вероятностей (обычно рассматривается равномерное распределение), и на практике реальное распределение входов может оказаться совсем другим. (Иногда его можно преобразовать в равномерное, используя датчик случайных чисел.)

Порядок роста

Наш анализ времени работы процедуры Insertion-Sort был основан на нескольких упрощающих предположениях. Сначала мы предположили, что время выполнения г-ж строки постоянно и равно С{. Затем мы огрубили оценку до an2 А-ЬпА-с. Сейчас мы пойдём ещё дальше и скажем, что время работы в худшем случае имеет порядок роста (rate of growth, order of growth) га2, отбрасывая члены меньших порядков (линейные) и не интересуясь коэффициентом при га2. Это записывают так: Т(п) = 0(га2) (подробное объяснение обозначений мы отложим до следующей главы).

Алгоритм с меньшим порядком роста времени работы обычно предпочтителен: если, скажем, один алгоритм имеет время работы 0(га2), а другой - 0(га3), то первый более эффективен (по крайней мере для достаточно длинных входов; будут ли реальные входы таковыми - другой вопрос).

Упражнения

1.2-1 Будем сортировать массив из га элементов так: просмотрим его и найдём минимальный элемент, который скопируем в первую ячейку другого массива. Затем просмотрим его снова и найдём следующий элемент, и так далее. Такой способ сортировки можно назвать сортировкой выбором (selection sort). Запишите этот алгоритм с помощью псевдокода. Укажите время его работы в лучшем и худшем случаях, используя О-обозначения.

1.2-2 Вернёмся к алгоритму линейного поиска (упр. 1.1-3).

Сколько сравнений потребуется в среднем этому алгоритму, если искомым элементом может быть любой элемент массива (с одинаковой вероятностью)? Каково время работы в худшем случае и в среднем? Как записать эти времена с помощью О-обозначений?

1.2-3 Дана последовательность чисел х±, Х2, , хп. Покажите, что за время ©(га log га) можно определить, есть ли в этой последовательности два одинаковых числа.

1.2-4 Даны коэффициенты ао, а\,..., ап-\ многочлена; требуется найти его значение в заданной точке х. Опишите естественный алгоритм, требующий времени ©(га2). Как выполнить вычисления за время О (га), не используя дополнительного массива? Используйте «схему Горнера»:

п-1

агхг = (... {an-ix + а„ 2)ж + ... + at)x + а0.

8 = 0

1.2-5 Как записать выражение га3/1000 - 100га2 - 100га + 3 с помощью О-обозначений?

1.2-6 Почти любой алгоритм можно немного изменить, радикально уменьшив время его работы в лучшем случае. Как?

1.3. Построение алгоритмов

Есть много стандартных приёмов, используемых при построении алгоритмов. Сортировка вставками является примером алгоритма, действующего по шагам (incremental approach): мы добавляем элементы один за другим к отсортированной части массива.

В этом разделе мы покажем в действии другой подход, который называют «разделяй и властвуй» (divide-and-conquer approach), и построим с его помощью значительно более быстрый алгоритм сортировки.

1.3.1. Принцип «разделяй и властвуй»

Многие алгоритмы по природе рекурсивны (recursive algorithms): решая некоторую задачу, они вызывают самих себя для решения её подзадач. Идея метода «разделяй и властвуй» состоит как раз в этом. Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются (с помощью рекурсивного вызова- или непосредственно, если размер достаточно мал). Наконец, их решения комбинируются и получается решение исходной задачи.

Для задачи сортировки эти три этапа выглядят так. Сначала мы разбиваем массив на две половины меньшего размера. Затем мы сортируем каждую из половин отдельно. После этого нам остаётся соединить два упорядоченных массива половинного размера в один. Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не дойдёт до единицы (любой массив длины 1 можно считать упорядоченным).

Нетривиальной частью является соединение двух упорядоченных массивов в один. Оно выполняется с помощью вспомогательной процедуры Merge (А, р, q, г). Параметрами этой процедуры являются массив А и числа р, q, г, указывающие границы сливаемых участков. Процедура предполагает, что р q < г и что участки А\р. .q] и A[q + 1. .г] уже отсортированы, и сливает (merges) их в один участок А[р..г].

Мы оставляем подробную разработку этой процедуры читателю (упр. 1.3-2), но довольно ясно, что время работы процедуры Merge есть ©(га), где га - общая длина сливаемых участков (га = г - Это легко объяснить на картах. Пусть мы имеем две стопки карт, и в каждой карты идут сверху вниз в возрастающем порядке. Как сделать из них одну? На каждом шаге мы берём меньшую из двух верхних карт и кладём её (рубашкой вверх) в результирующую стопку. Когда одна из исходных стопок становится пустой, мы добавляем все оставшиеся карты второй стопки к результирующей стопке. Ясно, что каждый шаг требует ограниченного числа действий, и общее число действий есть ©(га).

Теперь напишем процедуру сортировки слиянием Merge-Sort(A,р, г), которая сортирует участок А[р..г] массива А, не меняя остальную часть массива. При р г участок содержит максимум один элемент, и тем самым уже отсортирован. В противном случае мы отыскиваем число q, которое делит участок на две примерно равные части А[р..д] (содержит [га/2] элементов) и A[q + l..r] (содержит [п/2\ элементов). Здесь через [ж] мы обозначаем целую часть ж (наибольшее целое число, меньшее или равное ж), а через [ж] - наименьшее целое число, большее или равное ж.