Big O notation: различия между версиями
Материал из Поле цифровой дидактики
Patarakin (обсуждение | вклад) |
Patarakin (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
|Environment=Snap!, JavaScript, Python | |Environment=Snap!, JavaScript, Python | ||
}} | }} | ||
https://upload.wikimedia.org/wikipedia/commons/8/89/Big-O-notation.png | |||
Big O нотация нужна для описания сложности алгоритмов. | Big O нотация нужна для описания сложности алгоритмов. | ||
Обозначение «„O“ большое» введено немецким математиком Паулем Бахманом во втором томе его книги «Analytische Zahlentheorie» (Аналитическая теория чисел), вышедшем в 1894 году. | Обозначение «„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]] | ; [[Big O notation]] + [[JavaScript]] | ||
: https://habr.com/ru/post/444594/ | : https://habr.com/ru/post/444594/ | ||
; [[Как проверить массив на наличие дублей]] | ; [[Как проверить массив на наличие дублей]] | ||
Версия 19:15, 4 января 2023
| Описание | «O» большое — математические обозначения для сравнения асимптотического поведения (асимптотики) функций. Используются в различных разделах математики, но активнее всего — в математическом анализе, теории чисел и комбинаторике, а также в информатике и теории алгоритмов. |
|---|---|
| Область знаний | Информатика |
| Авторы | Бахман |
| Поясняющее видео | |
| Близкие понятия | Временная сложность алгоритма |
| Среды и средства для освоения понятия | Snap!, JavaScript, Python |
Big O нотация нужна для описания сложности алгоритмов. Обозначение «„O“ большое» введено немецким математиком Паулем Бахманом во втором томе его книги «Analytische Zahlentheorie» (Аналитическая теория чисел), вышедшем в 1894 году. Чтобы понять, что такое О большое, мы можем взглянуть на типичный пример O (n²), который обычно произносится как «Большой O в квадрате»
Определения
Пусть [math]\displaystyle{ f(x) }[/math] и [math]\displaystyle{ g(x) }[/math] — две функции, определенные в некоторой проколотой окрестности точки [math]\displaystyle{ x_0 }[/math], причем в этой окрестности [math]\displaystyle{ g }[/math] не обращается в ноль. Говорят, что:
- [math]\displaystyle{ f }[/math] является «O» большим от [math]\displaystyle{ g }[/math] при [math]\displaystyle{ x\to x_0 }[/math], если существует такая константа [math]\displaystyle{ C\gt 0 }[/math], что для всех [math]\displaystyle{ x }[/math] из некоторой окрестности точки [math]\displaystyle{ x_0 }[/math] имеет место неравенство
- [math]\displaystyle{ |f(x)| \leqslant C |g(x)| }[/math];
- [math]\displaystyle{ f }[/math] является «о» малым от [math]\displaystyle{ g }[/math] при [math]\displaystyle{ x\to x_0 }[/math], если для любого [math]\displaystyle{ \varepsilon\gt 0 }[/math] найдется такая проколотая окрестность [math]\displaystyle{ U_{x_0}' }[/math] точки [math]\displaystyle{ x_0 }[/math], что для всех [math]\displaystyle{ x\in U_{x_0}' }[/math] имеет место неравенство
- [math]\displaystyle{ |f(x)| \lt \varepsilon |g(x)|. }[/math]
Иначе говоря, в первом случае отношение [math]\displaystyle{ \frac{|f|}{|g|} \leqslant C }[/math] в окрестности точки [math]\displaystyle{ x_0 }[/math] (то есть ограничено сверху), а во втором оно стремится к нулю при [math]\displaystyle{ x\to x_0 }[/math].
