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


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

92 Глава 2. Основы анализа алгоритмов

Решение

С функциями f1, f2 и f все просто — они принадлежат базовым семействам экспо- ненциальных, полиномиальных и логарифмических функций. В частности, со- гласно (2.8), f4(n)=O(f2 (n)), а согласно (2.9), f,(n)=O(/фn)).

Разобраться с функцией f тоже не так уж сложно. Сначала она растет медлен- нее 10n, но после n > 10 очевидно 10n < nn. Это именно то, что нужно для определе- ния O(): для всех n > 10 выполняется условие 10n < cnn, где в данном случае c = 1, а значит, 10n = O(nn).

Остается функцияf5, которая выглядит, откровенно говоря, несколько странно. В таких случаях бывает полезно вычислить логарифм и посмотреть, не станет ли выражение более понятным. В данном случае lоg^(w) = ⅜/lоg, n = (log,;?)1/2. Как

выглядят логарифмы других функций? lоg^(w) = log, log,a logf,(п) = ~ 1й⅜ п. Все

3 '

эти выражения могут рассматриваться как функции log2 n; используя обозначение z = log2 n, получаем

Теперь происходящее становится более понятным. Прежде всего, для z > 16 имеем log2 z < z1/2. Но условие z > 16 эквивалентно n > 216 = 65 536; следовательно, после n > 216 выполняется условие \оgf(п) < lоg^(w), а значит, f(п) 29 = 512. Для n, больших этой границы, выполняется условие logf5(n) < logf 2(n); следовательно, f5(n)

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

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

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