Математическое толкование символа O

8. Используя математическую индукцию, докажите, что
для n  2.
Решение.
Доказательство.
Пусть S_n есть утверждение для n  2.
Базис индукции. Докажем S_1.
При n=2 посчитаем, чему равна левая часть равенства: .
Справа получаем
.
Так что S₁ истинно.
Индуктивный переход.
Предполагаем, что для любого k2 утверждение S_к истинно.
Это означает, что .
Теперь необходимо доказать, что S_к+1 истинно. Другими словами требуется доказать, что .
Используя предположение (1) и сравнивая это равенство с (2), замечаем, что, умножив обе части равенства (1) на , получим равенство (2).



9. Пусть X = {1, 2, 3, 4, 5, 6} и f – инъективная функция из X в множество–степень P(X), определенная следующим образом:
f(1) = {2,3,4},
f(2) = {1,4,2},
f(3) = {2,4},
f(4) = ,
f(5) = {1,2,3,4,6},
f(6) = {1,3,2}.
Опишите множество W, отсутствие отображения на которое гарантирует нам теорема 3.16 учебного пособия.
Решение.
Теорема 3.16. Никакое множество Х не равномощно множеств Р(х) всех своих подмножеств.
W={х | хХ и хf(х)}.
Тогда W={1,3,4,5,6} – множество из доказательства теоремы, и в него не отображается никакой элемент.


10. Расположите следующие 4 функции в порядке увеличения скорости роста (каждая функция есть O(следующая)), не исключено, что некоторые функции имеют одинаковую скорость:
f₁(n) = , f₂(n) = , f₃(n) = 2ⁿ, f₄(n) = n².
Решение.
Для оценки производительности алгоритмов можно использовать разные подходы. Самый бесхитростный - просто запустить каждый алгоритм на нескольких задачах и сравнить время исполнения. Другой способ - математически оценить время исполнения подсчетом операций.