Просмотр кода страницы Big O notation

{{Понятие
|Description=«O» большое  — математические обозначения для сравнения асимптотического поведения (асимптотики) функций. Используются в различных разделах математики, но активнее всего — в математическом анализе, теории чисел и комбинаторике, а также в информатике и теории алгоритмов.
|Field_of_knowledge=Информатика
|Inventor=Бахман
|Clarifying_video=https://www.youtube.com/watch?v=cXCuXNwzdfY
|similar_concepts=Временная сложность алгоритма
|Environment=Snap!, JavaScript, Python
}}
Big O нотация нужна для описания сложности алгоритмов. 
Обозначение «„O“ большое» введено немецким математиком Паулем Бахманом во втором томе его книги «Analytische Zahlentheorie» (Аналитическая теория чисел), вышедшем в 1894 году.
Чтобы понять, что такое О большое, мы можем взглянуть на типичный пример O (n²), который обычно произносится как «Большой O в квадрате»

== Определения ==
Пусть <math>f(x)</math> и <math>g(x)</math> — две функции, определенные в некоторой [[Окрестность#Проколотая окрестность|проколотой окрестности]] точки <math>x_0</math>, причем в этой окрестности <math>g</math> не обращается в ноль.
Говорят, что:
* <math>f</math> является «O» большим от <math>g</math> при <math>x\to x_0</math>, если существует такая константа <math>C>0</math>, что для всех <math>x</math> из некоторой окрестности точки <math>x_0</math> имеет место неравенство
*: <math>|f(x)| \leqslant C |g(x)|</math>;
* <math>f</math> является «о» малым от <math>g</math> при <math>x\to x_0</math>, если для любого <math>\varepsilon>0</math> найдется такая проколотая окрестность <math>U_{x_0}'</math> точки <math>x_0</math>, что для всех <math>x\in U_{x_0}'</math> имеет место неравенство
*: <math>|f(x)| < \varepsilon |g(x)|.</math>

Иначе говоря, в первом случае отношение <math>\frac{|f|}{|g|} \leqslant  C</math> в окрестности точки <math>x_0</math> (то есть ограничено сверху), а во втором оно стремится к нулю при <math>x\to x_0</math>.


; [[Big O notation]] + [[JavaScript]]
: https://habr.com/ru/post/444594/
; [[Как проверить массив на наличие дублей]]

----
https://upload.wikimedia.org/wikipedia/commons/8/89/Big-O-notation.png