ТЕМА 54 / 55 · ПУНКТ 57 10–15 минут
Асимптотическое сравнение функций
Сначала пойми идею. Затем попробуй рассказать доказательство своими словами и закрепи результат задачей.
Что означают буквы и значки7 обозначений
Здесь — обозначения, которые встретятся в этой теме. Точный смысл буквы уточняй по формуле рядом с ней.
- Произвольный элемент множества или число, с которым работаем.
- Небольшая положительная прибавка, которой сдвигаем число.
- Малое o: f=o(g) означает, что f/g → 0.
- Большое O: f=O(g) означает, что |f/g| ограничено.
- Функция: правило, которое каждому допустимому аргументу сопоставляет значение.
- Другая функция, например для сравнения или композиции с f.
- Обычно означает эквивалентность; в асимптотике — отношение функций стремится к 1.
ШАГ 01
Разбираемся в теме
Определение и обозначения
- При заданной базе означает , если финально.
- означает, что финально ограничено.
- означает .
- Здесь читают «мало о», — «большое о», — «эквивалентны».
Пример
При из пункта 55: и .
Из следует .
Факт
Если и , то .
РАЗБЕРИ ПО РИСУНКУ
Эквивалентность видна при увеличении масштаба
ДЛЯ УСТНОГО ОТВЕТА
Доказательство
- по арифметике пределов.
- Для сумм заменять слагаемые эквивалентными опасно из-за сокращения: , но , так что главный член исчезает.
Понял идею?Проверь себя на задаче или устном вопросе.