Độ phức tạp thuật toán

Tóm tắt lại:
- Big-O , Omega, Theta đều là $\lim n\to \infty$
- Big-O của $f(n)$ là $g(n)$ khi: $f(n)\le C. g(n)$
- Big-Omega của f(n) là g(n) khi: $f(n)\ge C. g(n)$
- Big-Theta của f(n) là g(n) khi: $C1 .g(n) \le f(n) \le C2. g(n)$
a) Với mọi số thực $x$ kí hiệu $\left \lfloor x \right \rfloor$ là số nguyên lớn nhất nhỏ hơn hoặc bằng $x$, chứng minh rằng $\left \lfloor n^2/3 \right \rfloor=\Theta (n^2),$ trong đó $n$ là số nguyên không âm.



Giải
Theo tính chất phần nguyên sàn ta có
$$x+1>\left \lfloor x \right \rfloor > x-1 \Rightarrow \frac{(n+1)^2}{3} >\left \lfloor \frac{n^2}{3} \right \rfloor> \frac{(n-1)^2}{3}$$
$$\frac{(n+1)^2}{3}<n^2,\; \forall n>2; \frac{(n-1)^2}{3}>\frac{n^2}{6} ,\;\;\forall n>10$$
$\left \lfloor \frac{n^2}{3} \right \rfloor$ có $O(n^2)$ và $\Omega(n^2)$


Vậy
$$\Rightarrow \left \lfloor \frac{n^2}{3} \right \rfloor= \Theta(n^2)$$

b) Giả sử $t(n)$ và $g(n)$ là các hàm đối số $n$ nguyên không âm, chứng minh nếu $t(n)\in O(g(n))$ thì $g(n) \in \Omega (t(n))$
Giải
Do $t(n) \in O(g(n)) \Rightarrow t(n) \le C_1 g(n); \; \forall C_1 >0, n\ge N , N\in \mathbb{N}$

$$\Rightarrow \frac{1}{C_1}t(n) \le  g(n); \; \forall C_1 >0, n\ge N , N\in \mathbb{N}$$

Đặt $K=\frac{1}{C_1}$ ta có $K.t(n)\le g(n) \forall n\ge N,K>0$

Với mọi $n\ge N, C_1>0;K>0,$ thì ta có $g(n) \in \Omega (t(n))$.