Упражнения с решениями Упражнение с решением 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)
Еще по теме Упражнения с решениями Упражнение с решением 1:
- § 3. Исправление недостатков решения арбитражного суда. Дополнительное решение
- РЕШЕНИЕ
- РЕШЕНИЕ АЛЬТЕРНАТИВНОЕ
- ПРИНЯТИЕ РЕШЕНИЙ
- РЕШЕНИЯ КСУ
- Не избегайте принятия решений
- ПРИНЯТИЕ РЕШЕНИЙ ГРУППОВОЕ
- ЗАДАЧА: РЕШЕНИЕ
- Принять решение
- Управленческие решения
- Решение проблем
- КЛЮЧ К РЕШЕНИЮ ПРОБЛЕМ.
- Убеждения и решения