18.02.201811.11.2018

О малое и о большое для чайников – 11 класс. Алгебра и начала математического анализа. Практическое решение задач по курсу – О большое и о малое. Как сравнивать функции

• by alexxlab
• Комментариев к записи О малое и о большое для чайников – 11 класс. Алгебра и начала математического анализа. Практическое решение задач по курсу – О большое и о малое. Как сравнивать функции нет
• Советы абитуриенту

О-большое и связанные с ним обозначения

Пауль Бахман

Эдмунд Ландау

Здесь Вы найдете различные общепринятые обозначения (“О” большое и связанные с ним обозначения), введенные Паулем Бахманом и Эдмундом Ландау.

Бесконечные пределы

Самым распространенным случаем является употребление этих обозначений при . Мы сначала рассмотрим именно это.

Обозначение при означает, что при достаточно больших функция удовлетворяет условию , где — некоторая положительная постоянная.

Точнее, при , если существуют такие положительные постоянные и , что для всех , которые удовлетворяют условию .

Тогда как запись через “О” большое означает ограниченность сверху, обозначение означает ограниченность снизу. Опять же рассмотрим поведение функции на бесконечности. Говорят, что при , если существуют такие положительные постоянные и , что для любого .

Обозначение означает, что одновременно и .

Осталось еще два обозначения: (греческая буква омикрон) и (строчная греческая буква омега). Обозначение омикрон также называют “о” малым.

Говорят, что , если при частное стремится к нулю.

Говорят также, что , если это частное стремится к бесконечности.

Конечные пределы

Все приведенные выше идеи остаются практически теми же для конечных пределов, хотя технические детали определения и отличаются.

при , если существуют такие положительные постоянные и , что для всех , которые удовлетворяют условию .

при , если существуют такие положительные постоянные и , что для всех , которые удовлетворяют условию .

при , если при стремится к .

при , если при стремится к бесконечности.

Часто можно видеть такие утверждения, как без явных ограничений. В этих случаях необходимо из контекста определять, какой предел подразумевается.

Использование

Обозначение “O” большое является общепринятым и в математике, и в информатике. Однако некоторые другие обозначения являются общепринятыми только в одной из этих областей.

В информатике акцент делается почти всегда на поведение алгоритма с ростом размерности задачи , поэтому неявно считается, что стремится к бесконечности. Обозначения и гораздо чаще используются в информатике, чем в математике. Обозначение “о” малое в информатике используется редко.

В математике обозначение “О” большое является общим для бесконечных и конечных пределов. Обозначение “о” малое следующее по популярности. Обозначения и являются редкими.

Обозначение не является распространенным ни в информатике, ни в математике.

Источники: http://www.johndcook.com/asymptotic_notation.html

http://ru.wikipedia.org/wiki/«O»_большое_и_«o»_малое

hijos.ru

о большое — ПриМат

$\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.$

Примеры решения задач

Рассмотрим примеры задач, в которых могут использоваться эквивалентные функции и символы Ландау. Читателю с целью самопроверки предлагается решить данные примеры самому, а затем сверить свое решение с приведенным.

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}}}.$
   Решение

   $\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$
   

2. Найти предел $\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}}$
   

3. Найти предел $\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}$

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}$
   

5. Доказать, что $\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.$

Смотрите также

1. Тер-Крикоров А. М., Шабунин М.И. Курс математического анализа: Учеб. пособие для вузов. – 3-е изд., исправл. / А. М. Тер-Крикоров, М.И. Шабунин. – Москва: ФИЗМАТЛИТ, 2001. – 672 с. — С. 116-121.
2. Кудрявцев Л. Д. Курс математического анализа : учебник для вузов: В 3 т. Т. 1. Дифференциальное и интегральное исчисления функций одной переменной / Л. Д. Кудрявцев. — 5-е изд., перераб. и доп. — Москва: Дрофа, 2003. — 703 с. — С. 253-271.
3. Фихтенгольц Г. М. Курс дифференциального и интегрального исчисления: учеб. пособие для ун-тов и пед. ин-тов. Т. 1 / Г. М. Фихтенгольц. — 5-е изд., стереотип. — Москва: Физматгиз, 1962. — 607 с. — С. 136-146.

Эквивалентные функции и символы Ландау

Лимит времени: 0

Информация

Пройдите этот тест, чтобы проверить свои знания по только что прочитанной теме

Вы уже проходили тест ранее. Вы не можете запустить его снова.

Тест загружается…

Вы должны войти или зарегистрироваться для того, чтобы начать тест.

Вы должны закончить следующие тесты, чтобы начать этот:

Правильных ответов: 0 из 9

Ваше время:

Время вышло

Вы набрали 0 из 0 баллов (0)

Средний результат
Ваш результат

Ваш результат был записан в таблицу лидеров

1. С ответом
2. С отметкой о просмотре

Поделиться ссылкой:

ib.mazurok.com

Знай сложности алгоритмов / Хабр

Эта статья рассказывает о времени выполнения и о расходе памяти большинства алгоритмов используемых в информатике. В прошлом, когда я готовился к прохождению собеседования я потратил много времени исследуя интернет для поиска информации о лучшем, среднем и худшем случае работы алгоритмов поиска и сортировки, чтобы заданный вопрос на собеседовании не поставил меня в тупик. За последние несколько лет я проходил интервью в нескольких стартапах из Силиконовой долины, а также в некоторых крупных компаниях таких как Yahoo, eBay, LinkedIn и Google и каждый раз, когда я готовился к интервью, я подумал: «Почему никто не создал хорошую шпаргалку по асимптотической сложности алгоритмов? ». Чтобы сохранить ваше время я создал такую шпаргалку. Наслаждайтесь!

Поиск

Сортировка

Структуры данных

Кучи

Представление графов

Пусть дан граф с |V| вершинами и |E| ребрами, тогда

Нотация асимптотического роста

1. (О — большое) — верхняя граница, в то время как (Омега — большое) — нижняя граница. Тета требует как (О — большое), так и (Омега — большое), поэтому она является точной оценкой (она должна быть ограничена как сверху, так и снизу). К примеру, алгоритм требующий Ω (n logn) требует не менее n logn времени, но верхняя граница не известна. Алгоритм требующий Θ (n logn) предпочтительнее потому, что он требует не менее n logn (Ω (n logn)) и не более чем n logn (O(n logn)).
2. f(x)=Θ(g(n)) означает, что f растет так же как и g когда n стремится к бесконечности. Другими словами, скорость роста f(x) асимптотически пропорциональна скорости роста g(n).
3. f(x)=O(g(n)). Здесь темпы роста не быстрее, чем g (n). O большое является наиболее полезной, поскольку представляет наихудший случай.

Короче говоря, если алгоритм имеет сложность __ тогда его эффективность __

График роста O — большое

habr.com

о большое и о малое для чайников



В разделе Лингвистика на вопрос Почему новичков называют «чайниками»? заданный автором

Марина Большакова лучший ответ это Неопытный новичок часто закипает, а если его уличат в дилетантстве и глупости, то кипятится и плюется. Свисту от него много, а как крышку откроешь, обнаружишь что там только пар. Кроме того, если перевернуть чайник, то это просто похоже на голову. А постучишь, так и полное сходство обнаружишь.
Есть еще гипотеза.
Слово пришло из жаргона туристов/альпинистов. Загадочна природа новичка. Почему-то гордый своими первыми достижениями чайник любит фотографироваться в традиционной позе: одна рука уперта в бок, другая приветственно помахивает фотографу. При этом силуэт туриста напоминает чайник с ручкой на боку и вздернутым носиком. Зачастую, дополняет фотку шапочка с помпоном, изображавшим ручку на его крышке.
Источник:

Ответ от 22 ответа[гуру]

Привет! Вот подборка тем с ответами на Ваш вопрос: Почему новичков называют «чайниками»?

Ответ от

словосочетание[новичек]
Инженер -Пожалуй правее всех! +500 !

Ответ от Малорослый[новичек]
свистят много и не по делу

Ответ от Олька Южанина[новичек]
не каждые новички чайники

Ответ от Евровидение[новичек]
Потому что он кипит, когда что то не получается ВОТ САМОЕ ПРАВИЛЬНОЕ ОПРЕДеЛЕНИЕ! люди краикость сестра таланта!;)) )

Ответ от Ляля Лесковская[новичек]
этот “термин” пошел изначально из горных лыж, когда новички в дутых куртках, любили фотографироваться в характерной позе “одну руку на пояс, а в другой палка” на тени получался такой себе “Заварник” их стали называть чайниками, а потом слово распространилось на остальные области.

Ответ от Приленский Евгений[новичек]
потомучто мало что сооброжает!!

Ответ от Антон Холин[новичек]
если растучать по чайнику будет такой же звук, как если постучать по голове “чайника

“

Ответ от Анна Богачёва[новичек]
тупые

Ответ от Jakov Grinberg[гуру]
Это прозвище придумали автомобилисты про новичков за рулем
т. к. они что бы себя обозначить на дороге часто сиг на лили без всякого
повода. Получалось шума много толку мало

Ответ от Княжна Мэри[новичек]
чай-китай, ник-имя. китай-на уровне немцев-то бишь немых, отношение к ним было всегда снисходительно-панибратским, мол, малые народы, ещё и русский толком не секут-короче обычный образчик русского шовинизма.

Ответ от Ольга Чайкова[гуру]
Поддерживаю версию ИНЖЕНЕРА про туристов-новичков.

Ответ от Неизвестно[гуру]
Есть 2 типа людей: чайники и ламеры.
Из первых вырастают гуру, а вторые так и остаются ламерами.
Ламер (от пиндосск. lame — хромой, калечный; от немецк. lamer — лизать, (реже) ягненок, что тоже как бы намекает; в переводе с недословного жаргона — унылый или также — «криворукий» (комп. сленг) ) — человек, абсолютно некомпетентный в той или иной сфере, обычно в компьютерной, но твёрдо уверенный в обратном и не предпринимающий абсолютно никаких попыток что-нибудь узнать.

Альтернативные варианты определения:
Чайник — не знает, но хотел бы узнать; ламер не знает и знать не хочет.
Ламер — это чайник, который думает, что он — хакер.
Ламер — это чайник со свистком.

Ответ от Екатерина С[гуру]
Чайник человеческий
Из всех видов чайников именно человек-чайник представляет наибольшую загадку для ученых. Науке достоверно не известно ни место, ни время, ни цель происхождения данного биологического вида. Единственное, о чем более-менее точно говорят чайнологи, обладающие эзотерическими (скрытыми от непосвященных) знаниями, так это о том, что изначально понятие «чайник» употреблялось адептами тайного братства как синоним понятия «человек» (ведь не случайно оба слова: «чайник» и «человек» – начинаются на «ч» и заканчиваются на «к») . Не известно только, о каком виде человека идет речь. В результате долгих дискуссий, современными философами было выдвинуто три гипотезы по этому поводу:

– понятием «человек» («чайник» ) обозначали любого человека, независимо от его расы, возраста, пола, происхождения и принадлежности к братству посвященных;
– понятием «человек» («чайник» ) обозначали агентов чайнизма, ведущих свою подрывную и пропагандистскую деятельность в среде непосвященных;
– понятием «человек» («чайник» ) обозначали сверхчеловека, о котором говорил философ Ницше (один из членов братства Великого чайника) и который должен будет когда-то родиться и повернуть весь ход истории человечества, основав царство Чайника на планете.
Какое из этих утверждений находится ближе всего к истине, науке, к сожалению, не известно. Однако есть мнение о том, что в современном обществе понятие «чайник» частично утратило свое сакральное значение. Дело в том, что вследствие утечки информации из среды братьев-чайников, некоторые обычные люди стали называть себя чайниками. Это делалось для того, чтобы добавить себе авторитета в обществе, намекая на свою связь с великим братством. Первое время братство боролось с подобными явлениями, отправляя «самозванных» чайников на костер (именно этим в средние века занималась святая инквизиция, маскируя данные казни под борьбу с ведьмами, колдунами и прочей нечистью) . Впоследствии была выработана другая стратегия: вместо борьбы с теми, кто незаслуженно именовал себя чайником, было принято решение, наоборот, создать массовый общественный стереотип о том, что якобы понятие «чайник» не имеет никакого отношения в тайному обществу и вселенскому заговору. Специально для этого некоторые научные деятели, принадлежащие к братству, решили открыть человечеству часть своих тайных знаний в различных трактатах, объединенных в серию книг «для чайников» . Согласно одной из гипотез, первым свое знание решил выставить на всеобщее обозрение Билл Гейтс (один из великих магистров братства) , приказав своим сподвижникам рассказать «чайникам» о Windows’е, который на протяжение многих тысячелетий использовался исключительно посвященными (с целью тотального контроля за информацией и эволюцией человечества) и не был доступен широким слоям общества.
В результате, поставленная цель была достигнута: многие называют себя чайниками, но практически никто (из непосвященных) ничего достоверно не знает о тайном обществе, символика которого (в виде металлических или электрических чайников) имеется практически в каждом доме и напоминает о его существовании.

Ответ от Ёанта – Клаус[гуру]
Долго ждать пока скипит ..родит мысль

Ответ от Наталья Пехина[гуру]
потому что пока чай ник поймет, что от него требуется кипяток, проходит какое-то время.

Ответ от MarS[гуру]
Жаргон, сленг такой, работничков-спецов обычно тормознутых до трех лет стажа называют чайниками, в любой области деятельности, а неисправимых чайников – ламерами. Ты, например, в данном проекте уже “самовар”, пока долговато “закипаешь”, но очень бурно и весело, радуешь других своей деятельностью

Ответ от 2 ответа[гуру]

Привет! Вот еще темы с нужными ответами:

 

Ответить на вопрос:

22oa.ru

О малое и большое : Анализ-I

Ограниченность не предполагает существования предела, более того, выражение имеет смысл, когда просто бегает по какому-то множеству, при этом никуда не стремясь.

Можно считать, что .
Выражение , (или, более общо, по какой-нибудь базе ), означает, что (соответственно, ).
Запись , ( некоторое множество), означает, что функция ограничена на множестве . Когда пишут , (или, более общо, по какой-нибудь базе ), то это значит, что функция ограничена в некоторой проколотой окрестности точки (на некотором элементе базы ).

dxdy.ru

---