Упражнение с решением 2

Пусть f и g — две функции, получающие неотрицательные значения, и f = O(g). Покажите, что g = Ω(f).

Решение

Это упражнение помогает формализовать интуитивное ощущение, что O() и Ω() в некотором смысле противоположны.

Собственно, доказать его несложно, для этого достаточно развернуть определения.

Известно, что для некоторых констант c и n0 выполняется условие f (n) < cg(n)

для всех n > ;?0. Разделив обе стороны на с, можно сделать вывод, что g(п) > —f(п)

для всех n > n0. Но именно это и необходимо, чтобы показать, что g = Ω( f): мы установили, что g(п) не меньше произведения f(п) на константу (в данном случае

- ) для всех достаточно больших n (начиная с n0). с

Упражнения

1. В приведенном ниже списке указано время выполнения пяти алгоритмов (пред- полагается, что указано точное время выполнения). Насколько медленнее будет работать каждый из алгоритмов, если: (a) увеличить размер входных данных вдвое; (b) увеличить размер входных данных на 1?

2. Есть шесть алгоритмов, время выполнения которых приведено ниже. (Предпо- лагается, что указано точное количество выполняемых операций как функция размера данных n.) Предположим, имеется компьютер, способный выполнять 1010 операций в секунду, и результат должен быть вычислен не более чем за час. При каком наибольшем размере входных данных n результат работы каждого алгоритма может быть вычислен за час?

3.


Расположите функции из следующего списка по возрастанию скорости роста. Другими словами, если функция g(n) в вашем списке следует непосредственно после f (n), из этого следует, что f (n)=O(g(n)).

4. Расположите функции из следующего списка по возрастанию скорости роста. Другими словами, если функция g(n) в вашем списке следует непосредственно после f (n), из этого следует, что f (n)=O(g(n)).

5. Допустим, имеются функцииf и g, такие чтоf (n) = О(g(n)). Для каждого из следующих утверждений укажите, является оно истинным или ложным, и при- ведите доказательство или контрпример.

6. Рассмотрим следующую задачу: имеется массив A, состоящий из n целых чи- сел A[1], A[2], ..., A[n]. Требуется вывести двумерный массив B размером n χ n, в котором B[i, j] (для i < j) содержит сумму элементов массива от A[i] до A j], то есть суммуA[i] + A[i + 1] + ... + Aj]. (Для i >j значение элемента массива B[i, j] остается неопределенным, поэтому выводиться для таких элементов может что угодно.)

Ниже приведен простой алгоритм решения этой задачи.

Просуммировать элементы массива от A[i] до A[j]

Сохранить результат в B[i, j]

Конец For Конец For

(a) Для некоторой выбранной вами функции f приведите границу времени выполнения этого алгоритма в форме O(f (n)) для входных данных размера n (то есть границу количества операций, выполняемых алгоритмом).

(b) Для той же функции f покажите, что время выполнения алгоритма для входных данных размера n также равно Ω( f (n)). (Тем самым определяется асимптотически точная граница Θ( f (n)) для времени выполнения.)

(c) Хотя алгоритм, проанализированный в частях (a) и (b), является наи- более естественным подходом к решению задачи (в конце концов, он просто перебирает нужные элементы массива B и заполняет их значениями), в нем присутствуют избыточные источники неэффективности.

Предложите другой алгоритм для решения этой задачи с асимптотически лучшим временем вы- полнения. Другими словами, вы должны разработать алгоритм со временем выполнения О(g(n)), где limn^ g(n)/f (n) = 0.

7. Существует целый класс народных и праздничных песен, в которых каждый куплет представляет собой предыдущий куплет с добавлением одной строки. Например, песня «Двенадцать дней Рождества» обладает этим свойством; добравшись до пятого куплета, вы поете о пяти золотых кольцах, затем упо- минаются четыре дрозда из четвертого куплета, три курицы из третьего, две горлицы из второго и, конечно, куропатка из первого. Песня на арамейском языке «Хад гадья», распеваемая на Пасху, тоже обладает этим свойством, как и многие другие песни.

Обычно такие песни исполняются долго, несмотря на относительно короткий текст. Чтобы определить слова и инструкции для одной из таких песен, до- статочно указать новую строку, добавляемую в каждом куплете, не записывая заново все предшествующие строки. (Таким образом, строка «пять золотых колец» будет записана только один раз, хотя она присутствует в пятом и во всех последующих куплетах.)

В этом примере присутствует асимптотическое поведение, которое стоит про- анализировать. Для конкретности допустим, что каждая строка имеет длину, ограниченную константой с, и при исполнении песня состоит из n слов. Покажи- те, как записать слова такой песни в виде текста длиной f (n) для функции f (n) с минимально возможной скоростью роста.

8. Вы занимаетесь экстремальными испытаниями различных моделей стеклянных банок для определения высоты, при падении с которой они не разобьются. Те- стовый стенд для этого эксперимента выглядит так: имеется лестница с n ступе- нями, и вы хотите найти самую высокую ступень, при падении с которой банка останется целой. Назовем ее наивысшей безопасной ступенью.

На первый взгляд естественно применить бинарный поиск: сбросить банку со средней ступени, посмотреть, разобьется ли она, а затем рекурсивно повторить попытку от ступени n/4 или 3n/4 в зависимости от результата. Но у такого решения есть недостаток: вероятно, при поиске ответа будет разбито слишком много банок.

С другой стороны, если вы стремитесь к экономии, можно опробовать сле- дующую стратегию. Сначала банка сбрасывается с первой ступени, потом со второй и т. д. Высота каждый раз увеличивается на одну ступень, пока банка не разобьется. При таком подходе достаточно всего одной банки (как только она разобьется, вы получаете правильный ответ), но для получения ответа может потребоваться до n попыток (вместо log n, как при бинарном поиске).

Похоже, намечается компромисс: можно выполнить меньше попыток, если вы готовы разбить больше банок. Чтобы лучше понять, как этот компромисс рабо- тает на количественном уровне, рассмотрим проведение эксперимента с ограни- ченным «бюджетом» из к > 1 банок. Другими словами, нужно найти правильный ответ (наивысшую безопасную ступень), использовав не более к банок.

(a) Допустим, вам выделен бюджет к = 2 банки. Опишите стратегию поиска наивысшей безопасной ступени, требующую не более f(n) бросков для не- которой функции f(n) с менее чем линейной скоростью роста. (Иначе говоря, в этом случае limn^ f (n)/n = 0.)

(b) Теперь допустим, что доступен бюджет к > 2 банок с некоторым за- данным к. Опишите стратегию поиска наивысшей безопасной ступени с использованием не более к банок. Если обозначить количество бросков по вашей стратегии f(n), то функцииf1, f2, f3, ... должны обладать тем свой- ством, что каждая из них растет асимптотически медленнее предыдущей:

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

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

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