О малое и о большое для чайников: О большое и о малое
О большое и о малое
Определения
Определение о малого
Символом о малое обозначают любую бесконечно малую функцию o(f(x)) по сравнению с заданной функцией f( x) при аргументе, стремящемся к некоторому конечному или бесконечному числу x0.
Функция α называется бесконечно малой по сравнению с функцией f при :
при
(читается: « есть о малое от при »),
если существует такая проколотая окрестность точки , на которой
при ,
где – бесконечно малая функция при :
.
Заметим, что просто бесконечно малая функция при является бесконечно малой по сравнению с постоянной функцией, не равной нулю.
Если, в предыдущем определении, f является бесконечно малой функцией при , то говорят, что является бесконечно малой более высокого порядка, чем f при .
Определение О большого
Символом О большое обозначают любую функцию , ограниченную относительно функции при аргументе, стремящемся к некоторому конечному или бесконечному числу x0.
Функция f ограничена относительно функции g при x → x0:
при
(читается: « есть О большое от при »),
если функции f и g определены на некоторой проколотой окрестности точки и существует такое число C, что на этой окрестности выполняется неравенство:
.
Просто ограниченная, на некоторой проколотой окрестности точки , функция является ограниченной по сравнению с постоянной функцией, не равной нулю.
Функции f и g называются функциями одного порядка при :
при ,
если и при .
Функции f и g называются эквивалентными (асимптотически равными) при :
при ,
если на некоторой проколотой окрестности точки ,
при , причем
.
Свойства и теоремы
Теорема. Свойства о малого
1) Если , то при .
2) Если на некоторой проколотой окрестности точки ,
и , то
.
3.1) , где c ≠ 0 – постоянная.
3.2) ;
3.3) .
Доказательство ⇓
Свойства о малого, применяемые в степенных рядах
Здесь m и n – натуральные числа, .
;
;
, если ;
;
;
;
, где ;
, где c ≠ 0 – постоянная;
.
Для доказательства этих свойств нужно выразить о малое через бесконечно малую функцию:
, где .
Свойства эквивалентных функций
1) Свойство симметрии. Если, при , , то .
2) Свойство транзитивности. Если, при , и , то .
3) Если , то при .
Доказательство ⇓
Теорема о связи эквивалентных функций с о малым
Для того чтобы две функции и были эквивалентными (или асимптотически равными), необходимо и достаточно чтобы при выполнялось условие:
.
Доказательство ⇓
Это свойство часто записывают так:
.
При этом говорят, что является главной частью при . При этом главная часть определена не однозначно. Любая эквивалентная функция является главной частью к исходной.
В силу свойства симметрии:
.
Теорема о замене функций эквивалентными в пределе частного
Если, при , и и существует предел
, то существует и предел
.
Доказательство ⇓
В силу свойства симметрии эквивалентных функций, если не существует один из этих пределов, то не существует и другой.
Поскольку любая функция, определенная на некоторой проколотой окрестности точки , эквивалентна самой себе, то существуют пределы
.
Заменив функции g и g1 на 1/g и 1/g1, получим аналогичную теорему для произведения.
Если, при , и , то
.
Это означает, что если существует один предел, то существует и другой. Если не существует один из этих пределов, то не существует и второй.
Лемма. Признак функций одного порядка
Если существует конечный ненулевой предел
(Л1.1) ,
то функции f и g одного порядка при :
при .
Доказательство ⇓
Доказательство свойств и теорем
Теорема. Свойства о малого
Все свойства ⇑ 1) Если , то при .
Доказательство
Пусть . Это означает, что существует такая проколотая окрестность точки , на которой определено отношение и поэтому . Тогда на этой окрестности
,
где . По условию
.
Тогда .
Свойство 1) доказано.
2) Если на некоторой проколотой окрестности точки ,
и , то
.
Доказательство
Поскольку , то на рассматриваемой проколотой окрестности точки ,
.
Поскольку , то
.
Свойство 2) доказано.
3.1) , где c ≠ 0 – постоянная.
3.2) ;
3.3) .
Доказательство
3.1). Пусть . Согласно определению о малого,
,
где . Введем функцию . Тогда
.
Поскольку , то
.
Свойство 3.1) доказано.
3.2). Докажем, что .
Пусть . Согласно определению о малого,
,
где .
Тогда ,
где . Поскольку
, то
.
Свойство 3.2) доказано.
3.3). Докажем, что .
Пусть . Согласно определению о малого,
,
где ,
.
Согласно арифметическим свойствам предела функции,
.
Тогда .
Свойство 3.3) доказано.
Эквивалентные функции
Свойства эквивалентных функций
Все формулировки ⇑ 1) Свойство симметрии. Если, при , , то .
Доказательство
Поскольку при , , то согласно определению эквивалентной функции, существует такая проколотая окрестность точки , на которой
,
где .
Поскольку функция имеет отличный от нуля предел, то по теореме об ограниченности снизу функции, имеющей ненулевой предел, существует такая проколотая окрестность точки , на которой . Поэтому на этой окрестности . Следовательно, на ней определена функция . Тогда
.
Согласно теореме о пределе частного двух функций,
.
Свойство доказано.
2) Свойство транзитивности. Если, при , и , то .
Доказательство
3) Если , то при .
Доказательство
Поскольку существует предел , то существует проколотая окрестность точки , на которой определено частное и, следовательно, . Тогда на этой окрестности
. Поскольку , то . В силу свойства симметрии, .
Свойство доказано.
Теорема о связи эквивалентных функций с о малым
Все формулировки ⇑ Для того чтобы две функции и были эквивалентными (или асимптотически равными), необходимо и достаточно чтобы при выполнялось условие:
.
Доказательство
1. Необходимость. Пусть функции и являются эквивалентными при . Тогда
.
Поскольку , то
.
Тогда .
Необходимость доказана.
2. Достаточность. Пусть при ,
.
Тогда , где . Отсюда
.
Поскольку , то
.
Теорема доказана.
Теорема о замене функций эквивалентными в пределе частного
Все формулировки ⇑ Если, при , и и существует предел
, то существует и предел
.
Доказательство
Пусть, при , и . Тогда
, где
.
Поскольку существует предел , то существует такая проколотая окрестность точки , на которой функция определена и отлична от нуля. Поскольку , то, по теореме об ограниченности снизу функции, имеющей ненулевой предел, существует такая проколотая окрестность точки , на которой и, следовательно, . Тогда существует проколотая окрестность точки , на которой функция определена и отлична от нуля и, следовательно, определено частное :
.
Применяем арифметические свойства предела функции:
.
Теорема доказана.
Признак функций одного порядка
Все формулировки ⇑ Лемма
Если существует конечный ненулевой предел
(Л1.1) ,
то функции f и g одного порядка при :
при .
Доказательство
Использованная литература.
О.И. Бесов. Лекции по математическому анализу. Часть 1. Москва, 2004.
Л.Д. Кудрявцев. Курс математического анализа. Том 1. Москва, 2003.
С.М. Никольский. Курс математического анализа. Том 1. Москва, 1983.
Автор: Олег Одинцов. Опубликовано: Изменено:
«О» большое — простое объяснение с картинками
Бью Карнес — разработчик, ведущий
YouTube-канал сайта freeCodeCamp.org, — в своей
статье
«Big O Notation — Simply explained with illustrations and video»
попытался простыми словами объяснить
нотацию большого «О».
Нотация «О» большое используется для
выражения скорости алгоритма. Это важно
при оценке как чужих алгоритмов, так и
своих собственных. В этой статье я
объясню, что такое «О» большое, а также
приведу список наиболее часто встречающихся
значений большого «О» и соответствующих
этим значениям алгоритмов.
«О» большое.
Почти все иллюстрации в этой статье авторства Адитьи Бхаргавы, автора книги «Грокаем алгоритмы».
Время работы алгоритмов
растет с разной скоростью
У моего сына Иуды есть много игрушек.
Их просто миллиард! Даже удивительно,
как быстро ребенок может собрать такое
количество игрушек, если он первый внук
для обеих ветвей семейного древа.
В общем, у Иуды проблема. Когда к нему
приходят друзья и хотят поиграть с
какой-то определенной игрушкой, ее
поиски могут занять целую вечность.
Поэтому ему нужен алгоритм поиска,
который помог бы найти нужную игрушку
как можно быстрее. Он пытается выбрать
между двумя разными алгоритмами: простым
и двоичным.
Выбранный алгоритм должен быть и
точным, и быстрым. С одной стороны,
двоичный поиск быстрее. А у Иуды зачастую
бывает лишь 30 секунд на поиски — пока
его другу не станет слишком скучно
искать игрушку. С другой стороны, алгоритм
простого поиска легче написать, и шансы
сделать что-то неверно гораздо меньше.
Ведь если друг найдет баги в его коде,
это будет очень огорчительно! Чтобы
подойти к делу с максимальной точностью,
Иуда решает засечь время, за которое
каждый из алгоритмов справится со
списком из ста игрушек.
Давайте предположим, что проверка
одной игрушки занимает 1мс. Если Иуде
придется проверить все 100 игрушек путем
простого поиска, это займет 100мс. С другой
стороны, применяя двоичный поиск, нужно
проверить всего 7 игрушек (log2 100 это
примерно 7, мы здесь не будем вдаваться
в точную математику), а значит, на это
уйдет 7мс.
Но на самом деле в списке миллиард
игрушек. Сколько времени будет работать
алгоритм простого поиска, обрабатывая
такой список? А сколько времени понадобится
алгоритму двоичного поиска?
Время работы простого и
двоичного поиска со списком из 100
элементов
Иуда запускает двоичный поиск со
списком из 1 млрд. игрушек и на работу
этого алгоритма уходит 30мс (log2 1000000000
примерно равен 30). «32мс! — думает
он. — Сколько же времени понадобится
при простом поиске? Двоичный поиск
примерно в 15 раз быстрее простого, ведь
алгоритму простого поиска понадобилось
100мс на список из 100 элементов, а алгоритму
двоичного поиска — только 7мс. Значит,
простой поиск со списком из 1 млрд.
элементов займет 30мс*15 = 450мс, верно?
Это намного меньше 30 секунд, за которые
мой друг успеет устать». И Иуда решает
воспользоваться алгоритмом простого
поиска. Но был ли это правильный выбор?
Нет. Оказалось, что Иуда ошибся и,
возможно, потерял своего друга навсегда.
Время работы алгоритма простого поиска
со списком из 1 млрд. элементов это не
450мс, а 1млрд. миллисекунд, т. е., 11 дней!
Дело в том, что время работы двоичного
и простого поиска возрастает не одинаково.
Время работы растет с разной скоростью!
По мере увеличения количества элементов
время работы двоичного поиска будет
понемногу расти, но при этом время работы
простого поиска возрастает очень сильно.
То есть, когда число элементов в списке
возрастает, двоичный поиск внезапно
становится намного быстрее простого.
Так что Иуда ошибся, предполагая, что
двоичный поиск всегда в 15 раз быстрее
простого. Если брать список с 1 миллиардом
элементов, двоичный поиск будет уже
примерно в 33 миллиона раз быстрее
простого.
Вот поэтому очень важно знать, с какой
скоростью возрастает время работы
алгоритма в зависимости от размера
списка. И здесь выходит на сцену «О»
большое.
«О» большое говорит вам, насколько
быстр ваш алгоритм. Предположим, у вас
есть список с размером n (т. е., у
вас n элементов в этом списке).
Простому поиску нужно проверить каждый
элемент, поэтому ему понадобится
произвести n операций. Время работы
этого алгоритма, записанное при помощи
нотации «О» большого, составляет O(n).
Где же, собственно, время? Где секунды?
Здесь их нет. «О» большое не сообщает
вам скорость в секундах. Эта нотация
позволяет вам сравнивать количество
необходимых операций. Она говорит
вам о том, как быстро возрастает скорость
работы алгоритма.
Давайте рассмотрим еще один пример.
Двоичному поиску для проверки списка
из n элементов нужно осуществить
log n операций. Каково время работы
алгоритма, записанное в нотации «О»
большого? O(log n). В общем, принцип записи
следующий:
Эта запись сообщает вам количество
операций, которое осуществит алгоритм.
Называется все это нотацией ««О»
большое», потому что перед количеством
операций ставится заглавная буква «О».
«О» большое описывает
количество операций при наихудшем
сценарии
Предположим, вы ищете пользователя в
своей базе данных и при этом применяете
алгоритм простого поиска. Вы знаете,
что его скорость — O(n), то есть, в наихудшем
случае вашему алгоритму придется
проверить каждого пользователя в вашей
базе данных. Но допустим, вы ищете
пользователя с именем aardvark213, а он стоит
первым в списке. Вашему алгоритму не
придется проверять каждый элемент
списка, потому что он найдет нужного
пользователя с первой попытки. Итак,
время, которое потребовалось алгоритму,
это O(n) или O(1)? Ведь он нашел нужного
пользователя с первой же попытки?
Время работы простого поиска в нотации
«О» большое все равно O(n). В нашем случае
алгоритм нашел искомое сразу. Это
сценарий наилучшего случая. Но «О»
большое описывает наихудший сценарий.
То есть, можно сказать, что в наихудшем
случае алгоритму придется по одному
разу проверить каждого пользователя в
базе данных, и на это уйдет время O(n). Это
перестраховка: вы знаете, что скорость
работы простого поиска никогда не будет
меньше, чем O(n).
Самые распространенные
варианты «О» большого
Если шутка не понятна, почитайте о задаче коммивояжера.
Вот пять вариантов «О» большого,
которые встречаются чаще всего. Они
отсортированы от самого быстрого к
самому медленному:
- O(log n) — логарифмическое время.
Пример: двоичный поиск. - O(n) — линейное время. Пример: простой
поиск. - O(n * log n). Пример: быстрый алгоритм
сортировки, такой как quicksort (быстрая
сортировка). - O(n2) — квадратичное время. Пример:
медленный алгоритм сортировки, такой
как сортировка выбором. - O(n!) — факториальное время. Пример:
очень медленный алгоритм, такой как в
задаче
коммивояжера.
Визуализация разного времени
в нотации «О» большого
Предположим, вам нужно нарисовать
сетку с 16 ячейками и вы можете выбрать
для этого 5 разных алгоритмов (из списка
выше).
Первый алгоритм займет O(log n) времени.
Вы можете осуществлять 10 операций в
секунду. Чтобы нарисовать сетку из 16
ячеек, при времени O(log n) вам понадобится
осуществить 4 операции (log 16 с основанием
2 это 4). То есть, у вас на это уйдет 0,4с.
Что, если нужно нарисовать 1024 ячеек? На
это потребуется log 1024 = 10 операций, т. е.,
1с. Это первый алгоритм.
Второй алгоритм медленнее, его время
выполнения O(n). Чтобы нарисовать 16 ячеек,
понадобится 16 операций, а чтобы нарисовать
1024 ячейки — 1024 операции. Сколько это в
секундах?
На графиках вы можете увидеть скорость
всех алгоритмов, от самого быстрого до
самого медленного:
Есть и другие варианты времени
выполнения алгоритмов, но эти встречаются
чаще всего.
Конечно, это упрощение. На самом деле
вы не сможете так точно конвертировать
время, записанное при помощи «О» большого,
в количество операций, но это хорошая
прикидка.
Заключение
Вот основные вещи, которые нужно
усвоить:
- Скорость алгоритма измеряется не
в секундах, а в приросте количества
операций. - Мы говорим о том, как быстро возрастает
время работы алгоритма в зависимости
от увеличения объема входящих данных. - Время работы алгоритма выражается
при помощи нотации большого «О». - Алгоритм со скоростью O(log n) быстрее,
чем со скоростью O(n), но он становится
намного быстрее по мере увеличения
списка элементов.
О большое: что это такое, почему это важно, и почему это не важно.
Очень интересная статья Shen Huang о нотации О большое: Big O notation: why it matters, and why it doesn’t
В статье присутствует математические формулы, формальные определения, математические доказательства и т.п. При переводе возможно были допущены не точности в этих понятиях. Но тем не менее статья очень интересна для получения базовых знаний, о том что такое нотации Большое О, зачем оно нужно и какие бывают варианты нотаций.
Вы действительно понимаете что такое О большое (Big O)? Если это так, то эта статья поможет вам освежить ваши знания перед собеседованием. Если нет, эта статья расскажет вам о том что это такое и зачем нужно об этом знать.
Нотация О большое является одним из самых фундаментальных инструментов анализа сложности алгоритма. Эта статья написана с предположением, что вы уже являетесь программистом и за вашими плечами большое количество написанного кода. Кроме того, для лучшего понимания материала потребуется знания основ математики средней школы. И так если вы готовы, давайте начнем!
Picture of a Mandelbrot set, which relates to Complex Numbers and Recursions, Pixabay
Содержание
- Что такое нотация О большое и почему это важно
- Формальное определение обозначения О большое
- О большое (Big O), О малое (Little O), Омега (Omega) и Тета (Theta)
- Сравнение сложности между всеми нотациями
- Время и пространство сложности
- Лучшая, Средняя, Худшая, Ожидаемая Сложность
- Почему О большое может быть не важна
- Заключение…
1. Что такое нотация О большое и почему оно важно
«Нотация О большое — это математическая нотация, которая описывает ограничивающее поведение функции, когда аргумент стремится к определенному значению или бесконечности. Он является членом семейства нотаций, изобретенных Полом Бахманом, Эдмундом Ландау и другими, которые в совокупности называются нотациями Бахмана-Ландау или асимптотическими нотациями ».
Проще говоря, нотация О большое описывает сложность вашего кода с использованием алгебраических терминов.
Чтобы понять, что такое О большое, мы можем взглянуть на типичный пример O (n²), который обычно произносится как «Большой O в квадрате». Буква «n» здесь представляет размер входных данных, а функция «g (n) = n²» внутри «O ()» дает нам представление о том, насколько сложен алгоритм по отношению к количеству входных данных.
Типичным алгоритмом со сложностью O(n²) будет алгоритм сортировки выбором. Сортировка выбором — это алгоритм сортировки, который выполняет итерацию по списку, чтобы гарантировать, что каждый элемент с индексом i является i-м наименьшим/наибольшим элементом списка. Наглядный пример.
Алгоритм может быть описан следующим кодом. Чтобы убедиться, что i-й элемент является i-м наименьшим элементом в списке, этот алгоритм сначала просматривает список с помощью цикла for. Затем для каждого элемента он использует другой цикл for, чтобы найти наименьший элемент в оставшейся части списка.
SelectionSort(List) {
for(i from 0 to List.Length) {
SmallestElement = List[i]
for(j from i to List.Length) {
if(SmallestElement > List[j]) {
SmallestElement = List[j]
}
}
Swap(List[i], SmallestElement)
}
}В этом сценарии мы рассматриваем переменную List как входные данные, поэтому размер ввода n — это количество элементов внутри List. Предположим, что оператор if, а присвоение значения, ограниченное оператором if, занимает постоянное время. Затем мы можем найти О большое для функции SelectionSort, проанализировав, сколько раз выполняются операторы.
Сначала внутренний цикл for выполняет операторы внутри n раз. А затем, после увеличения i, внутренний цикл for выполняется n-1 раз … пока он не будет запущен еще один раз, тогда оба цикла for достигнут своих условий завершения.
Selection Sort Loops Illustrated
На самом деле это в конечном итоге дает нам геометрическую сумму, и благодаря математики средней школе мы обнаружим, что внутренний цикл будет повторяться 1 + 2… + n раз, что равно n(n-1)/2 раза. Если мы умножим это, мы получим n²/2-n/2.
Когда мы вычисляем О большое, мы заботимся только о доминирующих операторах, и не заботимся о коэффициентах. Таким образом, мы выбираем n² как О большое. Мы записываем его как O(n²), а произносим как «О большое в квадрате».
Теперь вам может быть интересно, что это за «доминирующие операторы»? И почему нас не волнуют коэффициенты? Не волнуйтесь, мы рассмотрим эти вопросы по очереди далее.
2. Формальное определение нотации О большое
Когда-то давно жил один индийский король, который захотел наградить мудреца. Мудрец попросил в качестве награды только пшеницы, которая бы заполнила все шахматную доску.
Но с определенным условием: в первой клетке должно быть 1 зернышко пшеницы, затем 2 зернышка на второй клетке, затем 4 на следующей … и так далее на каждой клетке шахматной доске должно быть вдвое больше количество зерен, чем на предыдущей. Наивный король согласился без колебаний, думая, что это слишком простое условие…
Wheat and Chess Board, Image from Wikipedia
Так сколько зерна пшеницы должен царь мудрецу? Мы знаем, что шахматная доска имеет 8 квадратов на 8 квадратов, что в сумме составляет 64 фишки, поэтому в итоговой фишке должно быть 2⁶⁴ зерна пшеницы. Если вы проведете самостоятельный расчет, вы получите 1,8446744 * 10¹⁹, то есть около 18, за которыми следуют 18 нулей. Предполагая, что каждое зерно пшеницы весит 0,01 грамма, это дает нам 184 467 440 737 тонн пшеницы. А 184 миллиарда тонн — это много, не правда ли?
Числа могут расти довольно быстро, не так ли? Та же логика относится и к компьютерным алгоритмам. Если требуемые усилия для выполнения задачи растут экспоненциально по отношению к размеру входных данных, алгоритм может в конечном итоге стать чрезвычайно затратным.
Если вы продолжите удвоение 2⁶⁴, то результат будет быстро потерян за пределами значащих цифр. Вот почему, когда мы смотрим на темпы роста, мы заботимся только о доминирующих операторах. И поскольку мы хотим проанализировать рост по отношению к размеру ввода, коэффициенты, которые только умножают число, и не растут с размером ввода, не содержат никакой полезной информации.
Ниже приведено формальное определение Большого O:
CSE 373 Slides from University of Washington
Формальное определение полезно, когда вам нужно выполнить математическое доказательство. Например, сложность для сортировки выбором может быть определена функцией f (n) = n²/2-n/2, как мы обсуждали в предыдущем разделе.
Если мы допустим, чтобы наша функция g(n) была n², мы можем найти константу c = 1 и N₀ = 0, при условии, N > N₀, где N² всегда будет больше, чем N²/2-N/2. Мы можем легко доказать это, вычитая N²/2 из обеих функций, тогда мы можем видеть, что N²/2 > -N/2 будет истинно, когда N>0. Поэтому мы можем прийти к выводу, что f(n) = O (n²), в другом порядке выбора это «О большое квадрат».
Вы могли заметить небольшую хитрость. То есть, если вы заставите g(n) расти быстрее, чем что-либо другое, O(g(n)) всегда будет достаточно большим. Например, для любой полиномиальной функции вы всегда будете правы, говоря, что оно являются O(2ⁿ), потому что 2ⁿ в конечном итоге будет всегда больше любого полинома.
С математической точки зрения вы будете правы, но обычно, когда мы говорим о Большом O, нам нужно знать жесткую границу (tight bound) функции. Вы узнаете об этом больше, в следующем раздел.
Но прежде чем мы пойдем дальше, давайте проверим ваше понимание следующим вопросом. Ответ будет приведен в следующем разделе.
Вопрос: Допустим изображение представлено двумерным массивом пикселей. Вы используете вложенный цикл for для итерации по каждому пикселю (то есть у вас есть цикл for, проходящий по всем столбцам, и другой цикл внутри, чтобы пройти по всем строкам). Какая в этом случае будет сложность алгоритма?
3. О большое, O малое, Омега и Тета
Ниже приведены формальные математические определения этих нотаций:
О большое: «f(n) есть O(g (n))» тогда и только тогда, когда некоторые константы c и N₀, f(N) ≤ cg(N) для всех N> N₀
Малое O: «f(n) есть o (g(n))», если f(n) есть O(g(n)) и f(n) не есть Θ(g(n))
Омега: «f(n) есть Ω(g(n))» тогда и только тогда, когда некоторые константы c и N₀, f(N) ≥ cg(N) для всех N> N₀
Тета: «f (n) есть Θ(g (n))» тогда и только тогда, когда f(n) есть O(g(n)), а f(n) есть Ω(g(n))
Простыми словами:
- О большое (O()) описывает верхнюю границу сложности.
- Малое O (o()) описывает верхнюю границу, исключая точную оценку.
- Омега (Ω ()) описывает нижнюю границу сложности.
- Тета (Θ ()) описывает точную оценку сложности.
Relationships between Big O, Little O, Omega & Theta Illustrated
Например, функция g(n) = n² + 3n — это O(n³), o(n⁴), Θ(n²) и Ω (n). Но вы все равно были бы правы, если бы сказали, что это Ω(n²) или O(n²).
Вообще, когда мы говорим о Большом O, мы на самом деле имеем в виду Тета (Θ Theta). Бессмысленно, когда вы определяете верхнюю границу, намного превышающую объем анализа. Это было бы похоже на решение неравенств путем помещения ∞ на большую сторону, что почти всегда формально сделает вас правым.
Но как определить, какие функции сложнее других?
4. Сравнение сложности между типичными нотациями Больших O
Когда мы пытаемся выяснить О большое для конкретной функции g(n), мы заботимся только о доминирующем операторе (dominant term) функции. Доминирующий оператор — это такой оператор, который растет быстрее всего.
Например, n² растет быстрее, чем n, поэтому, если у нас есть что-то вроде g(n) = n² + 5n + 6, то О большое будет (n²). Если вы когда нибудь проводили некоторые исчисления, это очень похоже на сокращение пределов для дробных многочленов, когда вам важен только доминирующий оператор для числителей и знаменателей в конце.
Another way to look at Big O, Image from Stack Overflow
Но какая функция растет быстрее, чем другие? На самом деле существует довольно много правил.
Complexity Growth Illustration from Big O Cheatsheet
1. O(1) имеет наименьшую сложность
Часто называемый «постоянный по времени», если вы можете создать алгоритм для решения проблемы с O(1), то это будет лучший выбор алгоритма. В некоторых сценариях сложность может выходить за пределы O(1), тогда мы можем проанализировать их, найдя ее аналог O(1/g(n)). Например, O(1/n) является более сложным, чем O(1/n²).
2. O (log(n)) является более сложным, чем O(1), но менее сложным, чем полиномы
Поскольку сложность часто связана с алгоритмами «разделяй и властвуй», O (log(n)) — это, как правило, хорошая сложность, которую можно достичь для алгоритмов сортировки. O (log(n)) является менее сложным, чем O (√n), потому что функцию квадратного корня можно считать полиномом, где показатель степени равен 0,5.
3. Сложность многочленов увеличивается с ростом степени
Например, O (n⁵) является более сложным, чем O (n⁴).
4. Экспоненты имеют большую сложность, чем полиномы, если коэффициенты положительные кратные n
O (2ⁿ) является более сложным, чем O (n⁹⁹), но O (2ⁿ) на самом деле является менее сложным, чем O(1). Обычно мы берем 2 в качестве основы для степеней и логарифмов, потому что в компьютерных науках все имеет тенденцию быть двоичным, но степень можно изменить, изменив коэффициенты. Если не указано иное, основание для логарифмов принимается равным 2.
5. Факториалы имеют большую сложность, чем степень
Если вам интересны доказательства, посмотрите Гамма-функцию (Gamma function), это аналитическое продолжение факториала. Краткое доказательство состоит в том, что и факториалы, и степень имеют одинаковое количество умножений, но числа, которые умножаются, растут для факториалов, оставаясь неизменными для степени.
6. Умножение
При умножении сложность будет больше, чем оригинал, но не больше, чем эквивалентность умножения чего-то более сложного. Например, O (n*log (n)) является более сложным, чем O (n), но менее сложным, чем O (n²), потому что O (n²) = O (n * n), а n более сложный, чем log (n). ).
Если хотите можете проверить свое понимание. Попробуйте ранжировать следующие функции от самых сложных до менее. Решения с подробными объяснениями можно будет найти в следующем разделе. Некоторые из них достаточно сложные и могут потребовать более глубокого понимания математики. Когда вы доберетесь до решения, вы узнаете об этом больше.
Вопрос: Расставьте следующие функции от самых сложных до менее.
Examples taken from Textbook Problems
Решение для вопроса из Раздела 2:
На самом деле это был вопрос с подвохом, чтобы проверить ваше понимание. Возможно вы бы предположили что ответ равен O (n²), потому что есть вложенный цикл for. Но нужно понять, что входными данными является массив изображений, и каждый пиксель в алгоритме проходится только один раз, то ответ на самом деле будет O (n). В следующем разделе будут рассмотрены другие примеры, подобные этому.
5. Время и пространство сложности
До сих пор мы обсуждали только временную сложность алгоритмов. То есть мы заботимся только о том, сколько времени потребуется программе для выполнения задачи. Что также важно, так это место, занимаемое программой в памяти для выполнения задачи. Сложность пространства связана с тем, сколько памяти будет использовать программа, и, следовательно, также является важным фактором для анализа.
Пространственная сложность работает аналогично временной сложности. Например, сортировка выбором имеет пространственную сложность O(1), потому что она хранит только одно минимальное значение и свой индекс для сравнения, максимальное используемое пространство не увеличивается с размером ввода.
Некоторые алгоритмы, такие как блочная сортировка, имеют пространственную сложность O (n), но при этом в ней можно уменьшить временную сложность до O (1). Блочная сортировка это такая сортировка в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо другим. Затем элементы помещаются обратно в массив.
Bucket Sort Visualization
6. Лучшая, Средняя, Худшая, Ожидаемая Сложность
Сложность также может быть проанализирована как лучший случай, наихудший случай, средний случай и ожидаемый случай.
Для примера давайте рассмотрим сортировку вставками (insertion sort). Сортировка вставками выполняет итерацию по всем элементам в списке. Если элемент больше, чем его предыдущий элемент, он вставляет элемент назад, пока он не станет больше, чем предыдущий элемент.
Insertion Sort Illustrated, Image from Wikipedia
Если массив изначально отсортирован, обмен вообще не будет произведен. Алгоритм будет просто пройдет итерацию по массиву один раз, что приведет к временной сложности O (n). Следовательно, мы бы сказали, что наилучшая временная сложность сортировки вставками — O (n). Сложность O (n) также часто называют линейной сложностью.
Иногда алгоритму может просто не повезти. Например, быстрая сортировка будет должна пройти через список за O (n), если элементы отсортированы в обратном порядке, но в среднем этот алгорит сортирует массив за O (n * log(n)). Как правило, когда мы оцениваем временную сложность алгоритма, мы смотрим на ее худшую производительность. Подробнее об этом и быстрой сортировке мы поговорим в следующем разделе.
Средняя сложность описывает ожидаемую производительность алгоритма. Иногда включает в себя расчет вероятности каждого сценария. Ниже приведена шпаргалка по временной и пространственной сложности типичных алгоритмов.
Big O Cheatsheet for Common Algorithms
Решение для вопроса из Раздела 4:
Осматривая функции, мы можем начать с ранжирования следующих полиномов от наиболее сложного до менее по правилу 3. Где корень квадратный из n равен просто n в степени 0,5.
Тогда, применяя правила 2 и 6, мы получим следующее. Логарифм с основанием 3 может быть преобразован в с основанием 2 (log base conversions). Логарифм с основанием 3 по-прежнему растет немного медленнее, чем с основанием 2, и поэтому в рейтинге получает место после него.
Остальные могут показаться немного сложными, но давайте попробуем быть немного повнимательнее и посмотреть, как же все такие их можно расположить.
Прежде всего, 2 в степени 2 в степени n больше 2 в степени n, а +1 еще больше его увеличивает.
Чтобы степень log (n) с основанием 2 была равна n, мы можем преобразовать следующее. Логарифм от 0,001 растет немного больше, чем просто константы, но меньше, чем почти все остальное.
Выражение, у которого n в степени log (log (n)), на самом деле является вариацией квазиполинома (quasi-polynomial), который больше полинома, но меньше экспоненты. Поскольку log (n) растет медленнее, чем n, его сложность немного меньше. Выражение с обратным логарифмом сходится к константе, поскольку 1 / log (n) расходится к бесконечности.
Факториалы могут быть представлены умножением и, следовательно, могут быть преобразованы в сложения вне логарифмической функции. «N select 2» может быть преобразовано в полином с кубическим членом, являющимся наибольшим.
И, наконец, мы можем ранжировать функции от самых сложных до наименее сложных.
Почему О большое может не имеет значения
!!! — WARNING — !!!
Идея, обсуждаемая далее, обычно не принимается большинством программистов в мире. Озвучивайте ее при собеседованиях на свой страх и риск. Бывали случаи когда, люди провалили собеседование в Google, потому что они подвергли сомнению необходимости нотаций.
!!! — WARNING — !!!
Поскольку ранее мы узнали, что сложность по времени в наихудшем случае для быстрой сортировки будет O (n²), а для сортировки слиянием (merge sort) будет O (n * log (n)), то сортировка слиянием должна быть быстрее, верно? Ну, вы, наверное, догадались, что ответ неверен. Чтобы это продемонстрировать, я выложил этот пример сюда trinket.io. Он сравнивает время для быстрой сортировки (quick sort) и сортировки слиянием (merge sort). Мне удалось протестировать его только на массивах длиной до 10000 значений, но, как вы можете видеть, время сортировки слиянием растет быстрее, чем быстрой сортировки. Несмотря на быструю сортировку, имеющую худшую сложность O (n²), вероятность этого действительно низка. Когда дело доходит до увеличения скорости, быстрая сортировка имеет более высокую скорость чем сортировка слиянием, ограниченная сложностью O (n * log (n)), быстрая сортировка заканчивается в среднем с лучшей производительностью.
Я также сделал график, чтобы сравнить соотношение между временем, которое они занимают, так как это время трудно увидеть при более низких значениях. И, как вы можете видеть, процент времени, требуемый для быстрой сортировки, очень быстро уменьшается.
Мораль этой истории в том, что нотация О большое — это всего лишь математический анализ, который дает представление о ресурсах, потребляемых алгоритмом. Практически результаты могут быть разными. Но, как правило, это хорошая практика — пытаться снизить сложность наших алгоритмов.
Заключение…
Мне нравится кодить, изучать новые вещи и делиться ими с сообществом. Если есть что-то, что вас особенно интересует, пожалуйста, дайте мне знать. Я обычно пишу о веб-дизайне, архитектуре программного обеспечения, математике и науке о данных. Вы можете найти несколько замечательных статей, которые я написал ранее, если вас интересует какая-либо из вышеперечисленных тем.
Была ли вам полезна эта статья?
[10 / 4.6]
О-большое и связанные с ним обозначения
Пауль Бахман
Эдмунд Ландау
Здесь Вы найдете различные общепринятые обозначения (“О” большое и связанные с ним обозначения), введенные Паулем Бахманом и Эдмундом Ландау.
Бесконечные пределы
Самым распространенным случаем является употребление этих обозначений при . Мы сначала рассмотрим именно это.
Обозначение при означает, что при достаточно больших функция удовлетворяет условию , где — некоторая положительная постоянная.
Точнее, при , если существуют такие положительные постоянные и , что для всех , которые удовлетворяют условию .
Тогда как запись через “О” большое означает ограниченность сверху, обозначение означает ограниченность снизу. Опять же рассмотрим поведение функции на бесконечности. Говорят, что при , если существуют такие положительные постоянные и , что для любого .
Обозначение означает, что одновременно и .
Осталось еще два обозначения: (греческая буква омикрон) и (строчная греческая буква омега). Обозначение омикрон также называют “о” малым.
Говорят, что , если при частное стремится к нулю.
Говорят также, что , если это частное стремится к бесконечности.
Конечные пределы
Все приведенные выше идеи остаются практически теми же для конечных пределов, хотя технические детали определения и отличаются.
при , если существуют такие положительные постоянные и , что для всех , которые удовлетворяют условию .
при , если существуют такие положительные постоянные и , что для всех , которые удовлетворяют условию .
при , если при стремится к .
при , если при стремится к бесконечности.
Часто можно видеть такие утверждения, как без явных ограничений. В этих случаях необходимо из контекста определять, какой предел подразумевается.
Использование
Обозначение “O” большое является общепринятым и в математике, и в информатике. Однако некоторые другие обозначения являются общепринятыми только в одной из этих областей.
В информатике акцент делается почти всегда на поведение алгоритма с ростом размерности задачи , поэтому неявно считается, что стремится к бесконечности. Обозначения и гораздо чаще используются в информатике, чем в математике. Обозначение “о” малое в информатике используется редко.
В математике обозначение “О” большое является общим для бесконечных и конечных пределов. Обозначение “о” малое следующее по популярности. Обозначения и являются редкими.
Обозначение не является распространенным ни в информатике, ни в математике.
Источники: http://www.johndcook.com/asymptotic_notation.html
http://ru.wikipedia.org/wiki/«O»_большое_и_«o»_малое
Что такое o-малое и O-большое ≪ ∀ x, y, z
Определение 1. Говорят, что функция есть о-малое от при , записывая это как при , если в некоторой окрестности верно равенство , где — бесконечно малая при .
Примечание. Данное определение задает целый класс функций, обладающих такими свойствами, поэтому правильнее было бы писать не , а , но исторически сложилась традиция писать равенство.
Утверждение 2. при тогда и только тогда, когда для любого найдется окрестность такая, что для любого верно неравенство .
Доказательство.
Пусть при в смысле первого определения, то есть в некоторой окрестности верно равенство , где — бесконечно малая при . Так как бесконечно малая, то для любого найдется окрестность такая, что для любого верно , а следовательно в этой окрестности верно неравенство .
Обратно, пусть для любого найдется окрестность такая, что для всех верно выполняется неравенство . Из этого неравенство следует, что , если . Определим функцию
Нетрудно проверить, что верно равенство , причем — бесконечно малая при .
Определение 3. Говорят, что функция есть О-большое от при , записывая это как при , если в некоторой окрестности верно равенство , где — ограниченная в .
Утверждение 4. при тогда и только тогда, когда найдется окрестность и константа такие, что для всех верно неравенство .
Доказательство.
Пусть при в смысле первого определения, то есть в некоторой окрестности верно представление , где — ограниченная в . Так как ограниченная в , то найдется константа такая, что для любого верно , а следовательно в этой окрестности верно неравенство .
Обратно, пусть есть окрестность и константа такие, что для всех верно неравенство . Из этого неравенство следует, что , если . Определим функцию
Нетрудно проверить, что верно равенство , причем — ограниченная в .
Определение 5. Говорят, что функция эквивалентна при , записывая это как при , если в некоторой окрестности верно равенство , где при .
Примеры
при .
при .
при (при любом ).
при .
при .
при .
при .
при .
о большое — ПриМат
$\DeclareMathOperator{\ctg}{ctg}\DeclareMathOperator{\tg}{tg} \DeclareMathOperator{\arctg}{arctg} \newcommand{\rndBrcts}[1]{\left ( #1 \right )} \newcommand{\abs}[1]{\left | #1 \right |}$Определение. Пусть функции $f$ и $g$ отличны от нуля в проколотой окрестности точки $x_0$ (равной, быть может, $+\infty,$ $-\infty$ или $\infty$). Говорят, что функции $f$ и $g$ эквивалентны при $x \to x_0,$ если $\lim\limits_{x \to x_0}\frac{f\rndBrcts{x}}{g\rndBrcts{x}} = 1.$ Обозначают это так: $f\rndBrcts{x} \sim g\rndBrcts{x} \ \rndBrcts{x \to x_0}.$
В терминах этого определения найденные ранее (см. Первый замечательный предел, Второй замечательный предел) пределы можно переписать следующим образом (все соотношения формулируются для случая $x \to 0$):
$$
\sin{x} \sim x, \\
\tg{x} \sim x, \\
1-\cos{x} \sim \frac{1}{2}x^2, \\
\arcsin{x} \sim x, \\
\arctg{x} \sim x, \\
a^x-1 \sim x \ln{a}, \\
\log_a{\rndBrcts{1+x}} \sim \frac{x}{\ln{a}}, \\ \
\rndBrcts{1+x}^\alpha-1\sim \alpha \cdot x.
$$
Эти соотношения останутся в силе, если в них вместо переменной $x$ записать отличную от нуля функцию $\varphi \rndBrcts{x},$ стремящуюся к нулю при $x \to x_0.$ Например, $\sin{x^2} \sim x^2 \ \rndBrcts{x \to 0},$ $\tg{\frac{1}{x}} \sim \frac{1}{x} \ \rndBrcts{x \to \infty},$ $\tg{\sin{\rndBrcts{x-1}^2}} \sim \sin{\rndBrcts{x-1}^2} \sim \rndBrcts{x-1}^2 \ \rndBrcts{x \to 1}.$
Теорема (применение эквивалентных функций для нахождения пределов). Пусть $f\rndBrcts{x} \sim f_1\rndBrcts{x}$ и $g\rndBrcts{x} \sim g_1\rndBrcts{x}$ при $x \to x_0$ и пусть существует $\lim\limits_{x \to x_0}\frac{f_1\rndBrcts{x}}{g_1\rndBrcts{x}} = A.$ Тогда существует $\lim\limits_{x \to x_0}\frac{f\rndBrcts{x}}{g\rndBrcts{x}} = A.$
По определению эквивалентных функций, используя арифметические свойства пределов, получаем
$$\lim\limits_{x \to x_0}\frac{f\rndBrcts{x}}{g\rndBrcts{x}} = \lim\limits_{x \to x_0}\frac{f\rndBrcts{x}}{f_1\rndBrcts{x}} \cdot \frac{g_1\rndBrcts{x}}{g\rndBrcts{x}} \cdot \frac{f_1\rndBrcts{x}}{g_1\rndBrcts{x}} = 1 \cdot 1 \cdot A = A,$$ и теорема доказана.
Доказанная теорема означает, что при вычислении пределов в произведении и в частном функции можно заменять эквивалентными. При этом существование предела и его величина не изменяются.
Пример.
$$\lim\limits_{x \to 0} \frac{\arcsin{x} \cdot \rndBrcts{e^x-1}}{1-\cos{x}} = \lim\limits_{x \to 0} \frac{x \cdot x}{\frac{x^2}{2}} = 2$$
Сравнение бесконечно больших и бесконечно малых
Символами Ландау называются символы $\overline{o}$ и $\underline O.$ Дадим определение.
Определение Пусть функции $f$ и $g$ определены в проколотой окрестности точки $x_0$ (конечного или бесконечного) и $g\rndBrcts{x} \neq 0.$ Говорят, что $f\rndBrcts{x}$ является $\overline{o}$-малой относительно $g\rndBrcts{x}$ при $x \to x_0,$ если $\lim\limits_{x \to x_0} \frac{f\rndBrcts{x}}{g\rndBrcts{x}} = 0.$ Обозначают это так: $f\rndBrcts{x} = \overline o\rndBrcts{g\rndBrcts{x}} \ \rndBrcts{x \to x_0}.$
Если $f\rndBrcts{x} \to 0, \ g\rndBrcts{x} \to 0$ и $f\rndBrcts{x} = \overline o\rndBrcts{g\rndBrcts{x}}$ при $x \to x_0,$ то говорят, что $f\rndBrcts{x}$ является бесконечно малой более высокого порядка, чем $g\rndBrcts{x},$ при $x \to x_0.$ Если же $f\rndBrcts{x} \to \infty, \ g\rndBrcts{x} \to \infty$ и $f\rndBrcts{x} = \overline o\rndBrcts{g\rndBrcts{x}} \text{ при } x \to x_0,$ то говорят, что $g\rndBrcts{x}$ стремится к бесконечности быстрее, чем $f\rndBrcts{x},$ при $x \to x_0.$ Например, $\sin \rndBrcts{x^2} = \overline o\rndBrcts{x} \ \rndBrcts{x \to 0}, \ \tg^3{x} \cdot \sin{\frac{1}{x}} = \overline o\rndBrcts{x^2} \ \rndBrcts{x \to 0}.$
Определение. Пусть функции $f$ и $g$ определены в проколотой окрестности $x_0$ (конечного или бесконечного) и $g\rndBrcts{x} \neq 0.$ Говорят, что $f\rndBrcts{x}$ является $\underline O$-большим относительно $g\rndBrcts{x}$ при $x \to x_0,$ если существует такая проколотая окрестность $U_{\delta}$ точки $x_0,$ что для всех $x \in U_{\delta}$ справедливо неравенство $\abs{f\rndBrcts{x}} \leqslant c \cdot \abs{g\rndBrcts{x}},$ где постоянная $c$ не зависит от $x$ (но может зависеть от окрестности $U_{\delta}$). Обозначают это так: $f\rndBrcts{x} = \underline O \rndBrcts{g\rndBrcts{x}} \ \rndBrcts{x \to x_0}.$
Например, $x^2+2x^3 = \underline O \rndBrcts{x^2}.$
Теорема. Пусть существует $\lim \limits_{x \to x_0} \abs{\frac{f\rndBrcts{x}}{g\rndBrcts{x}}} = K,$ где $0 \leqslant K \lt+\infty.$ Тогда $f\rndBrcts{x} = \underline O \rndBrcts{g\rndBrcts{x}}.$
Рассматриваем случай $x_0 \in \mathbb{R}.$ Зададим $\varepsilon = 1$ и найдем такое $\delta \gt 0,$ что для всех $x,$ удовлетворяющих условию $\abs{x-x_0} \lt \delta,$ справедливо неравенство $\abs{\abs{\frac{f\rndBrcts{x}}{g\rndBrcts{x}}}-K} \lt 1.$ Последнее неравенство равносильно тому, что
$$K-1 \lt \abs{\frac{f\rndBrcts{x}}{g\rndBrcts{x}}} \lt K+1.$$ Умножая правое неравенство на $\abs{g\rndBrcts{x}},$ получаем утверждение теоремы.
Теорема (критерий эквивалентности функций). Для того, чтобы отличные от нуля функции $f$ и $g$ были эквивалентны при $x \to x_0,$ необходимо и достаточно, чтобы было выполнено равенство $f\rndBrcts{x} = g\rndBrcts{x}+\overline o\rndBrcts{g\rndBrcts{x}} \ \rndBrcts{x \to x_0}.$
Необходимость. Пусть $f\rndBrcts{x} \sim g\rndBrcts{x}$ при $x \to x_0.$ Тогда $\frac{f\rndBrcts{x}}{g\rndBrcts{x}}-1 \to 0 \ \rndBrcts{x \to x_0},$ т. е. $\frac{f\rndBrcts{x}}{g\rndBrcts{x}}-1 = h\rndBrcts{x},$ где $h\rndBrcts{x} \to 0 \ \rndBrcts{x \to x_0}.$ Отсюда следует, что $f\rndBrcts{x} = g\rndBrcts{x}+g\rndBrcts{x} \cdot h\rndBrcts{x}.$ Но $\frac{g\rndBrcts{x} \cdot h\rndBrcts{x}}{g\rndBrcts{x}} = h\rndBrcts{x},$ т. е. $g\rndBrcts{x} \cdot h\rndBrcts{x} = \overline o\rndBrcts{g\rndBrcts{x}} \ \rndBrcts{x \to x_0}.$
Достаточность. Если $f\rndBrcts{x} = g\rndBrcts{x}+\overline o\rndBrcts{g\rndBrcts{x}} \ \rndBrcts{x \to x_0},$ то $\frac{f\rndBrcts{x}}{g\rndBrcts{x}} = 1+\frac{\overline o\rndBrcts{g\rndBrcts{x}}}{g\rndBrcts{x}}$ и поэтому $\lim\limits_{x \to x_0} \frac{f\rndBrcts{x}}{g\rndBrcts{x}} = 1.$
Используя эту теорему, набор эквивалентных функций, выписанный нами ранее, можно переписать в следующем виде (всюду $x \to 0$):
$$
\sin{x} = x+\overline o\rndBrcts{x}, \\
\tg{x} = x+\overline o\rndBrcts{x}, \\
1-\cos{x} = \frac{1}{2}x^2+\overline o\rndBrcts{x^2}, \\
\arcsin{x}= x+\overline o\rndBrcts{x}, \\
\arctg{x} = x+\overline o\rndBrcts{x},\\
a^x-1 = x \ln{a}+\overline o\rndBrcts{x}, \\
\log_a{\rndBrcts{1+x}} = \frac{x}{\ln{a}} + \overline o\rndBrcts{x}, \\
\rndBrcts{1+x}^\alpha-1 = \alpha \cdot x + \overline o\rndBrcts{x}.
$$
С помощью этой таблицы можно вычислять пределы. Покажем это на примерах.
Пример 1.$$\lim\limits_{x \to 0}\frac{e^x-\sqrt[3]{1+x}}{2 \arctg{x}-\arcsin{x}} = \lim\limits_{x \to 0}\frac{e^x-1-\rndBrcts{\sqrt[3]{1+x}-1}}{2 \arctg{x}-\arcsin{x}} = \\ = \lim\limits_{x \to 0}\frac{x+\overline o\rndBrcts{x}-\rndBrcts{\frac{1}{3}x+\overline o\rndBrcts{x}}}{2\rndBrcts{x+\overline o\rndBrcts{x}}-x+\overline o\rndBrcts{x}} = \lim\limits_{x \to 0}\frac{\frac{2}{3}x+\overline o\rndBrcts{x}}{x+\overline o\rndBrcts{x}} = \\ = \lim\limits_{x \to 0}\frac{\frac{2}{3}+\frac{\overline o\rndBrcts{x}}{x}}{1+\frac{\overline o\rndBrcts{x}}{x}} = \frac{2}{3}$$
Пример 2. Раскрытие неопределенности $\left [ 1^\infty \right ].$ Пусть $\alpha\rndBrcts{x} \to 0 \rndBrcts{\alpha\rndBrcts{x} \neq 0}, \ \beta\rndBrcts{x} \to \infty.$ Тогда, в силу непрерывности показательной функции,
$$\lim\limits_{x \to x_0}\rndBrcts{1+\alpha\rndBrcts{x}}^{\beta\rndBrcts{x}} = \lim\limits_{x \to x_0}e^{\beta\rndBrcts{x}\ln \rndBrcts{{1+\alpha\rndBrcts{x}}}} = e^{\lim\limits_{x \to x_0}\beta\rndBrcts{x}\rndBrcts{\alpha\rndBrcts{x}+\overline o\rndBrcts{\alpha\rndBrcts{x}}}}.$$ Если существует $\lim\limits_{x \to x_0}\alpha\rndBrcts{x}\cdot\beta\rndBrcts{x} = A,$ то
$$\lim\limits_{x \to x_0}\beta\rndBrcts{x}\rndBrcts{\alpha\rndBrcts{x}+\overline o\rndBrcts{\alpha\rndBrcts{x}}} = \\ =\lim\limits_{x \to x_0}\beta\rndBrcts{x}\cdot\alpha\rndBrcts{x}\cdot\frac{\alpha\rndBrcts{x}+\overline o\rndBrcts{\alpha\rndBrcts{x}}}{\alpha\rndBrcts{x}} = \\ = \lim\limits_{x \to x_0}\beta\rndBrcts{x}\cdot\alpha\rndBrcts{x}\cdot\rndBrcts{1+\frac{\overline o\rndBrcts{\alpha\rndBrcts{x}}}{\alpha\rndBrcts{x}}}= A.$$ Поэтому
$$\lim\limits_{x \to x_0}\rndBrcts{1+\alpha\rndBrcts{x}}^{\beta\rndBrcts{x}} = e^A.$$
Упражнение. Пусть $\lim\limits_{x \to x_0}\alpha\rndBrcts{x} = 0, \lim\limits_{x \to x_0}\beta\rndBrcts{x} = \infty.$ Доказать, что $\lim\limits_{x \to x_0}\rndBrcts{1+\alpha\rndBrcts{x}}^{\beta\rndBrcts{x}} = 0,$ если $\lim\limits_{x \to x_0}\alpha\rndBrcts{x}\cdot\beta\rndBrcts{x} = -\infty.$ Если же $\lim\limits_{x \to x_0}\alpha\rndBrcts{x}\cdot\beta\rndBrcts{x} = +\infty,$ то $\lim\limits_{x \to x_0}\rndBrcts{1+\alpha\rndBrcts{x}}^{\beta\rndBrcts{x}} = +\infty.$
Примеры решения задач
Рассмотрим примеры задач, в которых могут использоваться эквивалентные функции и символы Ландау. Читателю с целью самопроверки предлагается решить данные примеры самому, а затем сверить свое решение с приведенным.
- Найти предел $\lim\limits_{x \to 1}\displaystyle\frac{\rndBrcts{x^{2018}-2x+1} \rndBrcts{e^{x-1}-1}}{\rndBrcts{x-1}\sin{ \rndBrcts{x-1}}}.$
Решение$\lim\limits_{x \to 1}\displaystyle\frac{\rndBrcts{x^{2018}-2x+1} \rndBrcts{e^{x-1}-1}}{\rndBrcts{x-1}\sin{ \rndBrcts{x-1}}} = \\
= \left[
\begin{gathered}
\text{При }x \to 1\\
e^{x-1}-1 \sim x-1\\
\sin{\rndBrcts{x-1}} \sim x-1\\
\end{gathered}
\right ] = \\
= \lim\limits_{x \to 1}\displaystyle\frac{\rndBrcts{x^{2018}-2x+1} \rndBrcts{x-1}}{\rndBrcts{x-1}\rndBrcts{x-1}} = \\
= \lim\limits_{x \to 1}\displaystyle\frac{x^{2018}-2x+1}{x-1} = \\
= \left[
\begin{gathered}
\rndBrcts{x^{2018}-2x+1} \bigg|_{x=1} = 0 \\
\Leftrightarrow \\
\rndBrcts{x^{2018}-2x+1} \vdots \rndBrcts{x-1}\\
\text{Разделим многочлен} \rndBrcts{x^{2018}-2x+1} \\
\text{ на двучлен } \rndBrcts{x-1}\\
\text{при помощи схемы Горнера:}\\
\ \ \ 1 \ 0 \ 0 \ 0 \ \ldots \ 0 \ -2 \ 1\\
1 \ 1 \ 1 \ 1 \ 1 \ \ldots \ 1 \ -1 \ 0\\
\end{gathered}
\right ] = \\
= \lim\limits_{x \to 1}\frac{\rndBrcts{x-1}\rndBrcts{x^{2017}+x^{2016}\ldots+x^2+x-1}}{\rndBrcts{x-1}} = \\ = \lim\limits_{x \to 1}\rndBrcts{x^{2017}+x^{2016}+\ldots+x^2+x-1} = 2016$ - Найти предел $\lim\limits_{x \to +\infty} \rndBrcts{\cos{\frac{1}{\sqrt{x}}}}^x.$
Решение$\lim\limits_{x \to +\infty} \rndBrcts{\cos{\frac{1}{\sqrt{x}}}}^x = \lim\limits_{x \to +\infty}e^{x \ln{\cos{\frac{1}{\sqrt{x}}}}} =
e^{\lim\limits_{x \to +\infty}x \ln{\cos{\frac{1}{\sqrt{x}}}}} = \\ =
\left[
\begin{gathered}
\lim\limits_{x \to +\infty}x \ln{\cos{\frac{1}{\sqrt{x}}}} = \\ = \lim\limits_{x \to +\infty}x \ln{\rndBrcts{1+\rndBrcts{ \cos{\frac{1}{\sqrt{x}}}-1}}} = \\
= \left[
\begin{gathered}
\text{При } x \to +\infty \\
\ln{\rndBrcts{1 + \rndBrcts{ \cos{\frac{1}{\sqrt{x}}}-1}}} \sim \\ \sim \cos{\frac{1}{\sqrt{x}}}-1 = \\ = -2{\sin^2{\frac{1}{2\sqrt{x}}}} \sim \\ \sim -2 \cdot {\rndBrcts{\frac{1}{2\sqrt{x}}}}^2 = -\frac{1}{2x}
\end{gathered}
\right ] = \\
= \lim\limits_{x \to +\infty}\frac{-x}{2x} = -\frac{1}{2}
\end{gathered}
\right ]
= e^{-\frac{1}{2}}$ - Найти предел $\lim\limits_{x \to 0} \displaystyle\frac{\arctg{\rndBrcts{\rndBrcts{1+x}^3-1}}+2\tg{x}}{e^x-1+3\ln{\rndBrcts{1+x}}}.$
Решение$\lim\limits_{x \to 0} \displaystyle\frac{\arctg{\rndBrcts{\rndBrcts{1+x}^3-1}}+2\tg{x}}{e^x-1+3\ln{\rndBrcts{1+x}}} = \\
= \left[
\begin{gathered}
\text{При }x \to 0\\
\arctg{\rndBrcts{\rndBrcts{1+x}^3-1}} = \\ =\rndBrcts{1+x}^3-1 + \overline o\rndBrcts{\rndBrcts{1+x}^3-1} = \\
=\rndBrcts{1+x}^3-1+\overline o\rndBrcts{x} = \\ = 3x+\overline o\rndBrcts{x}+\overline o\rndBrcts{x}=3x+\overline o\rndBrcts{x}\\
\tg{x} = x+\overline o\rndBrcts{x}\\
e^x-1 = x+\overline o\rndBrcts{x}\\
\ln{\rndBrcts{1+x}} = x+\overline o\rndBrcts{x}
\end{gathered}
\right ] = \\
=\lim\limits_{x \to 0}\displaystyle\frac{3x+\overline o\rndBrcts{x}+2x+\overline o\rndBrcts{x}}{x+\overline o\rndBrcts{x}+3 \rndBrcts{x+\overline o\rndBrcts{x}}} =
\lim\limits_{x \to 0}\displaystyle\frac{5x+\overline o\rndBrcts{x}}{4x+\overline o\rndBrcts{x}} = \\ =\lim\limits_{x \to 0}\displaystyle\frac{5+\frac{\overline o\rndBrcts{x}}{x}}{4+\frac{\overline o\rndBrcts{x}}{x}}=\frac{5}{4}$ - Найти предел $\lim\limits_{x \to a} \displaystyle\frac{a^x-x^a}{x-a}, \ a \gt 0.$
Решение$\lim\limits_{x \to a} \displaystyle\frac{a^x-x^a}{x-a} = \lim\limits_{x \to a} \displaystyle\frac{\rndBrcts{a^x-a^a}-\rndBrcts{x^a-a^a}}{x-a} = \\ = \lim\limits_{x \to a} \displaystyle\frac{a^a\rndBrcts{a^{x-a}-1}-a^a\rndBrcts{\rndBrcts{\frac{x}{a}}^a-1}}{x-a} = \\
= \lim\limits_{x \to a}\displaystyle\frac{a^a\rndBrcts{a^{x-a}-1}-a^a\rndBrcts{\rndBrcts{1+\rndBrcts{\displaystyle\frac{x}{a}-1}}^a-1}}{x-a} = \\
= \left[
\begin{gathered}
\text{При }x \to a \\
a^{x-a}-1 = \rndBrcts{x-a}\ln{a}+\overline o\rndBrcts{x-a} \\
\rndBrcts{1+\rndBrcts{\frac{x}{a}-1}}^a-1 = \\
= a\rndBrcts{\frac{x}{a}-1}+\overline o\rndBrcts{\frac{x}{a}-1} = \\
= \rndBrcts{x-a}+\overline o\rndBrcts{x-a}
\end{gathered}
\right ] = \\
= \lim\limits_{x \to a} \frac{a^a\rndBrcts{\rndBrcts{x-a}\ln{a}+\overline o\rndBrcts{x-a}}-a^a\rndBrcts{\rndBrcts{x-a}+\overline o\rndBrcts{x-a}}}{x-a} = \\ = \lim\limits_{x \to a} \displaystyle\frac{a^a\rndBrcts{x-a}\rndBrcts{\ln{a}-1}+\overline o\rndBrcts{x-a}}{x-a} = \\
= a^a\rndBrcts{\ln{a}-1}$ - Доказать, что $\forall n \in \mathbb{N} \ \underbrace{\sqrt{x+\sqrt{x+\ldots+\sqrt{x}}}}_{n \text{ корней}} \sim \sqrt{x}$ при $x \to +\infty$
РешениеДокажем утверждение методом математической индукции по $n$ — количеству корней.
База индукции. При $n = 1$ имеем $\sqrt{x} \sim \sqrt{x},$ что, очевидно, верно в силу рефлексивности бинарного отношения эквивалентности функций.
Предположение индукции. Пусть утверждение верно для всех $n \leqslant k, \ k \geqslant 1.$
Шаг индукции. Докажем теперь утверждение для $n = k+1.$ Покажем, что $\underbrace{\sqrt{x+\sqrt{x+\ldots+\sqrt{x}}}}_{k+1 \text{ корень}} \sim \sqrt{x},$ что равносильно тому, что $\lim\limits_{x \to +\infty}\displaystyle\frac{\underbrace{\sqrt{x+\sqrt{x+\ldots+\sqrt{x}}}}_{k+1 \text{ корень}}}{\sqrt{x}}=1.$ Имеем: $\displaystyle\frac{\underbrace{\sqrt{x+\sqrt{x+\ldots+\sqrt{x}}}}_{k+1 \text{ корень}}}{\sqrt{x}} = \displaystyle\frac{\sqrt{x}\sqrt{1+\frac{{\underbrace{\sqrt{x+\sqrt{x+\ldots+\sqrt{x}}}}_{k \text{ корней}}}}{x}}}{\sqrt{x}} = \\ = \displaystyle\sqrt{1+\frac{{\underbrace{\sqrt{x+\sqrt{x+\ldots+\sqrt{x}}}}_{k \text{ корней}}}}{x}}.$
По индуктивному предположению $\underbrace{\sqrt{x+\sqrt{x+\ldots+\sqrt{x}}}}_{k \text{ корней}} \sim \sqrt{x},$ что по критерию эквивалентности означает, что $\underbrace{\sqrt{x+\sqrt{x+\ldots+\sqrt{x}}}}_{k \text{ корней}} = \sqrt{x}+\overline{o}\rndBrcts{\sqrt{x}} = \overline{o}\rndBrcts{x}.$ Тогда переходя к пределу имеем: $\lim\limits_{x \to +\infty}\displaystyle\frac{\underbrace{\sqrt{x+\sqrt{x+\ldots+\sqrt{x}}}}_{k+1 \text{ корень}}}{\sqrt{x}} = \lim\limits_{x \to +\infty}\sqrt{1+\frac{\overline{o}\rndBrcts{x}}{x}} = 1.$
Смотрите также
- Тер-Крикоров А. М., Шабунин М.И. Курс математического анализа: Учеб. пособие для вузов. – 3-е изд., исправл. / А. М. Тер-Крикоров, М.И. Шабунин. – Москва: ФИЗМАТЛИТ, 2001. – 672 с. — С. 116-121.
- Кудрявцев Л. Д. Курс математического анализа : учебник для вузов: В 3 т. Т. 1. Дифференциальное и интегральное исчисления функций одной переменной / Л. Д. Кудрявцев. — 5-е изд., перераб. и доп. — Москва: Дрофа, 2003. — 703 с. — С. 253-271.
- Фихтенгольц Г. М. Курс дифференциального и интегрального исчисления: учеб. пособие для ун-тов и пед. ин-тов. Т. 1 / Г. М. Фихтенгольц. — 5-е изд., стереотип. — Москва: Физматгиз, 1962. — 607 с. — С. 136-146.
Эквивалентные функции и символы Ландау
Лимит времени: 0
Информация
Пройдите этот тест, чтобы проверить свои знания по только что прочитанной теме
Вы уже проходили тест ранее. Вы не можете запустить его снова.
Тест загружается…
Вы должны войти или зарегистрироваться для того, чтобы начать тест.
Вы должны закончить следующие тесты, чтобы начать этот:
Правильных ответов: 0 из 9
Ваше время:
Время вышло
Вы набрали 0 из 0 баллов (0)
| Средний результат |
|
| Ваш результат |
|
Ваш результат был записан в таблицу лидеров
С ответом
С отметкой о просмотре
Поделиться ссылкой:
Помогите решить / разобраться (М)
Ну так почему бы не доопределить их для остальных точек?
Потому что получатся другие функции А я хочу сравнивать те, которые есть. По крайней мере, когда они тривиально сравнимы, как те, которые я в стартовом посте обозначил.
А если и доопределять, то как? До непрерывности? А это всегда будет возможно? Upd. ewert опередил.
oleg.k
Попробуйте другие уже готовые определения, по-моему это проще. После этого можете разбираться, насколько они эквивалентны.
Они не эквивалентны. Все на свой лад. У Фихтенгольца, например, сравниваются только бесконечно малые и бесконечно большие функции, стремящиеся к , определенные на одинаковых областях определения. Мне это тоже не нравится. У Зорича области определения сравниваемых функций не обязаны совпадать, как у Фихтенгольца, но он пишет
Зорич писал(а):
Эти функции могут даже иметь разные исходные области определения, но если мы интересуемся их асимптотическим поведением при базе , то нам важно только, чтобы все они были определены на некотором элементе базы . Учитывая, что у него обозначает базу проколотых окрестностей точки , то для 2-ух моих функций из стартового поста тоже получается, что сравнение не определено.
Но практически-то — зачем? Какая от этого польза для сельского хозяйства?
Из соображений общности. Если смотреть на все с позиции сельского хозяйства, то и предел надо определять только для функций (в одномерном анализе)
Шпаргалка по ландшафтному дизайну для чайников
- Дом и сад
- Садоводство
- Шпаргалка по ландшафтному дизайну для чайников
Филип Жиру, Боб Бекстром, Лэнс Уолхейм, редакторы Национальной садоводческой ассоциации
Создание идеального ландшафта начинается с составления списка желаний, адаптированного к вашим потребностям, планирования ландшафтного дизайна и покупки растений, наиболее подходящих для вашего ландшафтного плана и зона морозостойкости.
Создайте список желаний для ландшафтного дизайна
Составьте список желаний, когда вы приступите к планированию ландшафта, и используйте свое воображение, чтобы настроить ландшафт в соответствии с потребностями вашей семьи. Рассмотрим дождевые бочки, костровище или чашу для костра, беседку или даже небольшую теплицу. Продолжайте копать, пока у вас во дворе не будет всего, что вам нужно. Учтите это в своем списке желаний:
Достаточно лужайки для игры в улов
Кирпичный дворик или деревянный настил
Барбекю под открытым небом
Живая изгородь
Огороженный двор
Бассейн или спа
Сарай для хранения или горшок
Компостная куча
Пруд с рыбками или отражающий бассейн
Место, куда приходят в гости бабочки и птицы
Уединенный уголок с гамаком
Цветочный сад
Розарий
Участок свежих трав или ароматный сад
Огород или фруктовый сад
Сад на крыше
Луковичный сад с цветами, знаменующий начало нового сезона
Сад во внутреннем дворике с различными горшками, полными разноцветных растений
Полевые цветы
Засухоустойчивый сад
Как спланировать ландшафт
Планирование ландшафта помогает сохранить бюджет, найти подходящие деревья и растения для ваших нужд и сосредоточить внимание на вашем списке пожеланий по ландшафтному дизайну.Используйте следующие шаги при планировании ландшафта:
Измерьте текущий ландшафт и нарисуйте на бумаге приблизительный план.
Просмотрите свой список желаний.
Определите свой бюджет.
Добавьте к своему плану возможные конструкции (внутренний дворик, палубу, навес, скамейку, забор, бассейн или пруд) и дорожки.
Определите наличие солнца, полутени и тени для каждой области, где вы планируете выращивать растения.Определите свои хардины
.Шпаргалка по индексу
для чайников
Рассел Уайлд
Когда вы инвестируете в индексный фонд, вы инвестируете во весь индекс, а не в отдельные акции. Но сначала вам нужно знать, что искать в индексе, как выбрать лучшие фонды и как сохранить баланс ваших инвестиций.
Индексные инвестиции: 5 способов определить хороший индекс
Индексные инвестиции настолько хороши, насколько хорош индексный фонд, а индексный фонд может быть настолько хорош, насколько хорош индекс, стоящий за ним.Так что же такое индекс ? Это стандартная мера изменений в производительности внутри группы акций; эта группа служит ориентиром для фондового рынка в целом или для отдельных его частей. Вы не можете инвестировать в индекс, потому что это математическая мера.
Примеры индексов: промышленный индекс Доу-Джонса и S&P 500 в США, японский Nikkei 225 и британский FTSE 100. (числа представляют количество акций в пределах этого конкретного индекса.)
Ниже приведены пять способов определить качество в индексе:
Хороший индекс — прозрачный. Вы точно знаете, сколько ценных бумаг он держит и какие именно ценные бумаги.
Оборот минимальный. Если половину ценных бумаг в индексе необходимо заменять каждый год, управляющему фондом, отслеживающему индекс, придется много покупать и продавать. Это увеличивает ваши расходы и настраивает вас на неприятный укус налогов.
Индекс логический. Ценные бумаги выбираются по некоторой объективной оценке, а не в результате какого-то конкурса популярности, который похож на выбор комитетом по выпуску школьного ежегодника самых красивых.
Лучшая ширина. Индекс включает достаточно ценных бумаг, чтобы точно представить конкретный рынок, и чем шире рынок, тем лучше. Десять акций или облигаций не представляют собой рынок. Индекс должен отражать значительную часть экономики.
Индекс актуален для реального мира. Отслеживает ли индекс что-то, что имеет смысл в вашем портфолио? Индекс, отслеживающий цены на маринованную свеклу или семена трав, может быть интересен, но действительно ли вы хотите поставить на него свою пенсию?
5 советов по выбору лучших индексных фондов
Когда вы будете готовы инвестировать в индексные фонды, приготовьтесь провести небольшое исследование. Выбор из примерно 300 индексных паевых инвестиционных фондов и более 700 ETF (торгуемых на бирже фондов) может быть сложной задачей.С чего начать?
Начните с типа инвестиций , который вам нужен для вашего портфеля. Если вам нужен долгосрочный рост, вам нужны акции. Если вам нужна стабильность, вам нужны облигации. Если у вас уже есть портфель из одного или другого, вам следует попытаться уравновесить это. Внутри этих двух больших категорий акций и облигаций вам нужна диверсификация. Вам нужны как американские, так и иностранные акции, и вам нужны акции как крупных, так и малых компаний.
Решите, хотите ли вы индексный паевой фонд или биржевой фонд (ETF). Это второстепенный, но важный вопрос. ETF могут иметь более низкие операционные расходы, но их покупка и продажа обходятся в несколько долларов. Они часто являются вашим лучшим вариантом для долгосрочных инвестиций по принципу «купи и держи», не требуя вмешательства или исправления, но не лучший вариант для счетов, где вы регулярно делаете взносы или снимаете средства. Если вы инвестируете в налогооблагаемый счет, ETF могут быть немного более эффективными с точки зрения налогообложения.
Всегда обращайте внимание на чистую прибыль. Если вы решите, что хотите, например, ETF, который отражает S&P 500, вы найдете множество возможностей, даже если все фонды будут примерно одинаковыми. Сразу исключите все фонды загрузки и обязательно сравните годовые эксплуатационные расходы.
Изучите указатель за сценой. Прочный дом опирается на прочный фундамент, как и солидный индексный фонд. Основой является сам индекс, будь то S&P 500 или любое количество менее известных индексов.
А как насчет возврата? Индексный фонд будет работать так же, как индекс, который он представляет, за вычетом расходов фонда. Можно ожидать, что в долгосрочной перспективе акции принесут больше прибыли, чем облигации (с большей волатильностью). Можно ожидать, что фонды акций с малой капитализацией будут работать лучше в долгосрочной перспективе, чем фонды акций с большой капитализацией (также с большей волатильностью).
L ong run означает много лет, поэтому не стоит слишком беспокоиться о том, что индексный фонд возвратил за последние месяцы или даже за последние год или два.Такие цифры во многом не имеют значения. Большинство инвесторов бросаются в горячие сектора. . . часто, поскольку эти сектора вот-вот остынут. Не поддавайтесь стремлению к высокой прибыли.
2 Методы ребалансировки ваших инвестиций в индекс
Неспособность перебалансировать свой инвестиционный портфель индекса может означать, что вы берете на себя дополнительный риск, поскольку ваша диверсификация исчезает и вы становитесь слишком зависимыми от одного или нескольких типов инвестиций.Например, ваши акции с большой капитализацией могут превзойти ваши акции с малой капитализацией. Ваши иностранные акции могут быть лучше, чем ваши внутренние. Или ваши облигации могут вырасти, а ваши акции — упасть.
Ребалансировка также вынуждает вас, несмотря на то, что вам говорят ваши эмоции, продавать недавних перевыполненных и скупать отстающих. С годами вы будете покупать дешево, а продавать дорого. Этот процесс покупки по низкой цене и продажи по высокой, иногда известный как бонус за ребалансировку , , может добавить целую процентную точку к вашей долгосрочной среднегодовой доходности.
Есть два способа перебалансировать ваш портфель. У обоих методов есть свои поклонники, и ни один из них не обязательно лучше другого. Каждый подход довольно прост, особенно когда ваш портфель состоит из грамотно выбранных индексных фондов, которые представляют четкие и понятные классы активов:
Календарный метод: Этот более распространенный метод заключается в атаке распределения вашего портфеля в соответствии с календарем. Большинство финансовых консультантов предлагают проводить ребалансировку каждый год или каждые 18 месяцев, причем последнее подходит большинству людей.Если вы живете за счет своего портфеля и вам нужно регулярно собирать деньги, вы можете подумать о том, чтобы сделать это накануне
.