Что не является непренебрежимо малыми функциями?

• Незначительная функция: Функция $\му$ является незначительный если $\forall c \in N \;\; \существует n_0 \в N$ такой, что $\forall n \geq n_0, \mu(n) < n^{âc}.$

  Как мы обычно сейчас делаем, пренебрежимо малая функция меньше любого многочлена. У нас также есть эквивалентное определение предела;

  $ф(п)$ является незначительный чем для каждого многочлена $ д (п) $ у нас есть;

  $$\lim_{n \rightarrow \infty} q(n) f(n) =0$$

  Простые примеры — это $2^{-n},2^{-\sqrt{n}}, \text{ и } n^{- \log n}$.

• Незначительная функция:^* функция $\му(п)$ является существенный если $\существует c \in N$ такой, что $\forall n_0 \in N, \существует n \geq n_0$ такой, что $\mu(n) \geq n^{-c}.$

  Чтобы не быть незначительным, достаточно только одного кандидата, чтобы показать, что $n \geq n_0$ для которого $\mu(n) \geq n^{-c}$.

• Заметная функция: Функция $\му$ является заметный если $\существует c \in N, n_0 \in N$ такой, что $\forall n \geq n_0, \mu(n) \geq n^{-c}.$

  Как видим, отличие от непренебрежимости есть; для всех $n \geq n_0$

  Примером является $n^{-3}$ который только полиномиально медленный (как и любой полином)

  Слабые односторонние функции определяются на заметных функциях.

Чередование является ключом к созданию отличительных примеров. Возьмите любую заметную и незначительную функцию и чередуйте их;

$$\mu(n) = \cases{ 2^{-n} & : $x$ четно \ n^{-3} & : $x$ нечетно}$$

$\му$ это незначительная и незаметная функция!.

_{^*Отрицание квантификаторов: В отрицании $\neg\forall = \exists$ и $\neg \exists = \forall$}