chức năng không đáng kể là gì?

• Chức năng không đáng kể: một chức năng $\mu$ Là không đáng kể nếu $\forall c \in N \;\; \exists n_0 \in N$ như vậy mà $\forall n \geq n_0, \mu(n) < n^{âc}.$

  Như chúng ta thường thấy bây giờ, một hàm không đáng kể nhỏ hơn bất kỳ đa thức nào. Chúng tôi cũng có một định nghĩa giới hạn tương đương;

  $f(n)$ Là không đáng kể hơn cho mọi đa thức $q(n)$ chúng ta có;

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

  Các ví dụ dễ hiểu là $2^{-n},2^{-\sqrt{n}}, \text{ và } n^{- \log n}$.

• Chức năng không đáng kể:^* một chức năng $\mu(n)$ Là không đáng kể nếu $\exists c \in N$ như vậy mà $\forall n_0 \in N, \exists n \geq n_0$ như vậy mà $\mu(n) \geq n^{-c}.$

  Không thể bỏ qua, chỉ một ứng cử viên là đủ để cho thấy rằng $n \geq n_0$ mà $\mu(n) \geq n^{-c}$.

• Chức năng đáng chú ý: một chức năng $\mu$ Là đáng chú ý nếu $\exists c \in N, n_0 \in N$ như vậy mà $\forall n \geq n_0, \mu(n) \geq n^{-c}.$

  Như chúng ta có thể thấy, sự khác biệt so với tính không đáng kể là; cho tất cả $n \geq n_0$

  Một ví dụ là $n^{-3}$ chỉ chậm về mặt đa thức (giống như bất kỳ đa thức nào)

  Chức năng một chiều yếu được xác định trên các chức năng đáng chú ý.

Xen kẽ là chìa khóa để tạo ra các ví dụ phân biệt. Lấy bất kỳ chức năng đáng chú ý và không đáng kể nào và xen kẽ chúng;

$$\mu(n) = \cases{ 2^{-n} & : $x$ là số chẵn \ n^{-3} & : $x$ là số lẻ}$$

$\mu$ là một chức năng không đáng kể và không đáng chú ý!.

_{^*phủ định định lượng: Trong phủ định $\neg\forall = \exists$ và $\neg \exists = \forall$}