Phân tích (thời gian) thuật toán về cơ bản là đếm số thao tác cơ bản mà thuật toán thực hiện. Tuy nhiên, việc đếm chính xác số thao tác cơ bản nhiều lúc không tầm thường hoặc phụ thuộc vào dữ liệu đầu vào (ví dụ lệnh if-then-else). Do đó, trong thực tế phân tích thuật toán, ta chỉ đếm tương đối số thao tác cơ bản mà thôi. Big-O $O(.)$ chính là một công cụ cho phép chúng ta biểu diễn tương đối độ phức tạp của thuật toán một cách đơn giản. Bài này chúng ta sẽ tìm hiểu định nghĩa hình thứ của các khía niệm $O(.), o(.), \Omega(.), \Theta(.)$. Mình đã viết một bài khác giải thích đầy đủ hơn các khái niệm này cũng nhưng các sử dụng trong phân tích thuật toán.

$O$-notation

 
Ví dụ 1:$T(n) = 3n^2 + 2n +4 \Rightarrow T(n) = O(n^2)$ vì $3n^2 + 2n +4$ < $4n^2$ với mọi $n \geq 1000$. Ở đây ta chọn $c= 4, n_0 = 1000$.

Ví dụ 2: $T(n) = 3n^2 + 2n +4 \Rightarrow T(n) = O(n^3)$ vì $3n^2 + 2n +4$ < $n^3$ với mọi $n \geq 1000$. Ở đây ta chọn $c= 1, n_0 = 1000$.

$\Omega$-notation

 
$\Theta$-notation

 
hoặc một cách định nghĩa tương tự như hai định nghĩa đầu tiên, đó là:

 
hoặc:

 
Bài tập: Chứng minh định nghĩa 3, 4 và 5 là tương đương.

 
$o$-notation

 
Cách định nghĩa khác là

 
Bài tập: Chứng minh định nghĩa 6 và 7 là tương đương.

Ví dụ 6: $T(n) = 3n^2 + 2n +4 \Rightarrow T(n) = o(n^3)$ (tại sao?)Hình minh họa các khái niệm:

Tham khảo

[1] Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001) [1990]. Introduction to Algorithms (2nd ed.) . MIT Press and McGraw-Hill. ISBN 0-262-03293-7
[2] Avrim Blum: Lecture notes on Algorithms, http://www.cs.cmu.edu/afs/cs/academic/class/15451-f11/www/lectures/lects1-10.pdf . Carnegie Mellon University, 2011.

Bài Tập

Bài tập 1: Hàm $f(n)$ tăng nhanh hơn $g(n)$ nếu $g(n) = O(f(n))$. Sắp xếp các hàm sau theo thứ tự tăng dần của độ tăng
(a) $(\frac{3}{2})^n \quad n^3 \quad \log^2 n \quad \log (n!) \quad 2^{2^n} \quad n^{\frac{1}{\log n}}$
(b) $(2)^{\log n} \quad (\log n)^{\log n} \quad e^n \quad 4^{\log n} \quad (n+1)! \quad \sqrt{\log n}$

Bài tập 2: Những kết luận sau đúng hay sai? Chứng minh.
(a) $f(n) = O(g(n)) \Rightarrow g(n) = O(f(n))$
(b) $f(n) + g(n) = \Theta(\min(f(n),g(n)))$
(c) $f(n) = O(g(n)) \Rightarrow 2^{f(n)} = O(2^{g(n)})$
(d) $f(n) = \Theta(f(n/2))$

 
Bài tập 1 và 2 được lấy từ Introduction to Algorithms, 2nd.