Упражнения с решениями Упражнение с решением 1

Имеется массив A из n элементов, в которых хранятся несовпадающие числа. Из- вестно, что последовательность значений A[1], A[2], ..., A[n] унимодальна: для не- которого индекса p в диапазоне от 1 до n значения в элементах массива возрастают до позиции P, а затем убывают до позиции n.
(Если нарисовать график, на котором ось x представляет позицию элемента в массиве j, а ось у — значение элемента A[j], график будет возрастать до точки p на оси x, где достигается максимум, а затем будет непрерывно убывать.)

Требуется найти «пиковый элемент» 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).

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Упражнения с решениями Упражнение с решением 1:

  1. § 3. Исправление недостатков решения арбитражного суда. Дополнительное решение
  2. РЕШЕНИЕ
  3. РЕШЕНИЕ АЛЬТЕРНАТИВНОЕ
  4. ПРИНЯТИЕ РЕШЕНИЙ
  5. РЕШЕНИЯ КСУ
  6. Не избегайте принятия решений
  7. ПРИНЯТИЕ РЕШЕНИЙ ГРУППОВОЕ
  8. ЗАДАЧА: РЕШЕНИЕ
  9. Принять решение
  10. Управленческие решения
  11. Решение проблем
  12. КЛЮЧ К РЕШЕНИЮ ПРОБЛЕМ.
  13. Убеждения и решения
  14. Убеждения и решения
  15. НАЙДИТЕ РЕШЕНИЕ
  16. НАЧНИТЕ С ПРИНЯТИЯ РЕШЕНИЯ
  17. Получение информации и принятие решений
  18. Решение измениться