[Phân tích thuật toán] Tiệm cận (Asymptotic notation)

Ở bài này, mình sẽ nói về độ phức tạp của một thuật toán. Do mình cũng mới nghiên cứu để viết bài này nên chưa thể hiểu rõ được, nhưng mình sẽ cố viết một cách dễ hiểu, có thể sẽ có sai sót, mong mọi người thông cảm và góp ý. Mọi người ráng đọc vậy, hơi dài

• Khi phân tích một thuật toán, một trong những vấn đề quan trọng nhất mà ta quan tâm là thời gian chạy (running time). Thời gian chạy của một thuật toán dựa trên nhiều yếu tố, ví dụ như tốc độ của máy tính, ngôn ngữ lập trình (C/C++, Python, blah blah blah, không phải tiếng Anh tiếng Miên gì nhá), compiler và blah blah blah, nói chung là nhiều yếu tố.

=> Vậy tiệm cận (Asymptotic) là một khái niệm giúp ta ước lượng được thời gian chạy (running time) của một thuật toán, thông qua số chỉ thị (machine instructions) hay gọi đơn giản là số bước.

Bây giờ hãy xem xét (chữ đầu là "xờ" nhé, chuyển thành "sờ" là có chuyện ngay) kỹ về thời gian chạy (đây là lần cuối mình mở ngoặc và thêm chữ running time). Chúng ta phải nghĩ về 2 thứ

Ta phải xác định, với kích thước của input (dữ liệu nhập), thuật toán sẽ chạy bao lâu. Ví dụ như số bước thực hiện tối đa của Binary Search hay Linear Search tăng theo chiều dài của dãy số (mảng). Vì thế ta nghĩ về thời gian chạy của một thuật toán như là một hàm về kích thước của dữ liệu nhập .

Ví dụ như ta có hàm F(n) = 9n² + 6n + 9 với n là kích thước *tối đa của dữ liệu nhập thì hàm F(n) chính là running time

• Thứ 2, ta tập trung vào ý nghĩ: khi kích thước input tăng thì thì tốc độ của thuật toán sẽ tăng nhanh như thế nào. Hay như ví dụ trên: Khi n (kích thước tối đa của input) tăng thì giá trị của hàm F(n) sẽ bao như thế nào (ví dụ n tăng 2 thì nguyên hàm đó tăng 4, đại loại thế). Và chúng ta gọi nó là Tỷ suất gia tăng, hay gọi cho đơn giản là rate of grow (mọi người luyện tiếng Anh chút vậy).

• Để dễ quản lý, ta lược bỏ các phần ít quan trọng trong cái hàm đi. Ví dụ như với kích thước input là n, ta tốn 9n2 + 6n + 9 bước thì phần n2 lớn hơn phần 6n + 9 (chú ý là đến 1 giá trị n nào đó thì nó mới lớn hơn, và từ đó trở đi sẽ luôn lớn hơn nữa. Mọi người học lại sách toán 9 để vẽ đồ thị sẽ rõ ).

• Vì thế ta bỏ phần hệ số (số 9) cùng phần 6n + 9 đi, chỉ giữ lại n2. Và ta nói rằng Running time của thuật toán này là n2

Và theo kinh nghiệm thì ta luôn lấy biến có bậc cao nhất làm running time. Và khi ta bỏ đi phần hệ số cũng như phần ít quan trọng hơn kia, thì lúc này, chúng ta có thể làm việc với chúng qua một thứ gọi là: Asymptotic notation, hay là các ký hiệu tiệm cận (cái tên tiếng Việt nghe không lọt lỗ tai)

Asymptotic notation gồm các dạng:

• Big-Theta:

• Big-O: thường được viết là O()

• Big-Omega:

Chú ý: - Do diễn đàn không hỗ trợ viết các notation này (mà có thì cũng chẳng mấy ai viết đâu, tốn thời gian lắm) nên sau này khi dùng đến chúng, hãy viết như mình viết ở trên.- Giữa 2 chữ có dấu gạch nối nhé (Big-O, Big-Theta, Big-Omega)- Sau các notation trên đều có đóng mở ngoặc đơn, bên trong là số liệu (ví dụ: O(n) )

Về các loại notation trên, mình sẽ nghiên cứu và viết về chúng sau. Cám ơn mọi người

Chết, quên ghi nguồn:http://khanacademy.org