Упражнения с решениями Упражнение с решением 1
Требуется найти «пиковый элемент» p без чтения всего массива, более того, нужно ограничиться чтением минимально возможного количества элементов A. Покажите, как найти p чтением не более О(log n) элементов A.
Решение
Сначала обсудим, как вообще добиться времени выполнения О(log n), а затем вер- немся к конкретной задаче. Чтобы выполнить некоторые вычисления так, чтобы количество операций не превышало O(log n), можно воспользоваться полезной стратегией, упоминавшейся в главе 2: выполнить постоянный объем работы, от- бросить половину входных данных и продолжить рекурсивную обработку остатка.
Например, именно эта идея обеспечила время выполнения О(log n) для бинарного поиска.
Происходящее можно рассматривать как проявление принципа «разделяй и властвуй»: для некоторой константы с > 0 выполняются не более с операций, после чего выполнение продолжается рекурсивно для входных данных, размер которых не превышает n/2. Мы будем считать, что рекурсия завершается при n = 2, выполняя максимум c операций для завершения вычислений. Если обо- значить T(n) время выполнения для входных данных с размером n, то мы имеем рекуррентное отношение (5.16)
Это рекуррентное отношение нетрудно разрешить методом раскрутки, как по- казано ниже.
♦ Анализ нескольких начальных уровней: на первом уровне рекурсии имеется одна задача с размером n, которая выполняется за время c плюс время, потраченное на все последующие рекурсивные вызовы. На следующем уровне имеется одна задача с размером не более n/2, которая добавляет еще с, а на следующем уров- не — одна задача с размером не более n/4, добавляющая еще с.
♦ Выявление закономерности: на сколько бы уровней мы ни продолжали анализ, на каждом уровне будет только одна задача: на уровне j будет одна задача с размером не более n/2j, которая вносит вклад с во время выполнения неза- висимо от j.
♦ Суммирование по всем уровням рекурсии: каждый уровень рекурсии добавляет максимум с операций, и для сокращения n до 2 потребуются log2 n уровней ре- курсии. Следовательно, общее время выполнения не превышает с, умноженного на количество уровней рекурсии, то есть максимум с log2 n = О(log n).
К тому же результату также можно прийти частичной подстановкой. Предполо- жим, T(n) < k logb n, причем k и b неизвестны. Если предположить, что это условие выполняется для меньших значений n в индукции, получим
Первое слагаемое в правой части — то, что нам нужно, остается выбрать k и b для компенсации добавления с в конце. Это можно сделать, выбрав b = 2 и k = с, так что k logb 2 = с log2 2 = с. Приходим к решению T(n) < с log n, которое полностью совпадает с тем, которое было получено при раскрутке рекуррентного отношения.
Наконец, стоит упомянуть, что ко времени выполнения О(log n) можно прийти при помощи практически таких же рассуждений в более общем случае, когда на каждом уровне рекурсии отбрасывается любая постоянная часть входных данных,
а экземпляр с размером n преобразуется в экземпляр с размером не более an для некоторой константы a < 1. Теперь для сокращения n до постоянного размера по- требуется не более log., n уровней рекурсии, а каждый уровень рекурсии требует /•'∙ 1/a
не более c операций.
Вернемся к нашей задаче. Чтобы использовать (5.16), можно было бы проверить среднюю точку массива и попытаться определить, лежит «пиковый элемент» до или после середины.
Допустим, мы обращаемся к значению А[n/2]. По одному этому значению невозможно определить, лежит p до или после n/2, поскольку еще нужно опре- делить, к какой половине относится n/2 — «восходящей» или «нисходящей». Соответственно мы проверяем значения А[n/2 - 1] и А[n/2 + 1]. Возможны три варианта.
♦ Если А[n/2 - 1] < А[n/2] < А[n/2 + 1], значит, n/2 следует строго перед p, и вы- полнение можно рекурсивно продолжить для элементов с n/2 + 1 до n.
♦ Если А[n/2 - 1] > А[n/2] > А[n/2 + 1], значит, n/2 следует строго после p, и вы- полнение можно рекурсивно продолжить для элементов с 1 до n/2 - 1.
♦ Наконец, если .4 [n/2] больше .4 [n/2 - 1] и А[n/2+ 1], выполнение завершено: «пиковым элементом» в данном случае является n/2.
Во всех перечисленных случаях выполняется не более трех обращений к мас- сиву А, а задача сводится к задаче с размером не более половинного. Это позволяет применить (5.16) и сделать вывод, что время выполнения составляет O(log n).
Еще по теме Упражнения с решениями Упражнение с решением 1:
- § 3. Исправление недостатков решения арбитражного суда. Дополнительное решение
- РЕШЕНИЕ
- РЕШЕНИЕ АЛЬТЕРНАТИВНОЕ
- ПРИНЯТИЕ РЕШЕНИЙ
- РЕШЕНИЯ КСУ
- Не избегайте принятия решений
- ПРИНЯТИЕ РЕШЕНИЙ ГРУППОВОЕ
- ЗАДАЧА: РЕШЕНИЕ
- Принять решение
- Управленческие решения
- Решение проблем
- КЛЮЧ К РЕШЕНИЮ ПРОБЛЕМ.
- Убеждения и решения
- Убеждения и решения
- НАЙДИТЕ РЕШЕНИЕ
- НАЧНИТЕ С ПРИНЯТИЯ РЕШЕНИЯ
- Получение информации и принятие решений
- Решение измениться