Chương 1. Thuật toán và phân tích thuật toán thông số nhận được khi chạy các dữ liệu này ta sẽ có một đánh giá về thuật toán. Tuy nhiên, phương pháp thực nghiệm có một số nhược điểm sau khiến nó khó có khả năng áp dụng trên thực tế: • Do phải cài đặt bằng một ngôn ngữ lập trình cụ thể nên thuật toán sẽ chịu sự hạn chế của ngôn ngữ lập trình này. • Hiệu quả của thuật toán sẽ bị ảnh hưởng bởi trình độ của người cài đặt.
• Việc chọn được các bộ dữ liệu thử nghiệm đặc trưng cho tất cả tập các dữ liệu vào của thuật toán là rất khó khăn và tốn nhiều chi phí. • Các số liệu thu nhận được phụ thuộc nhiều vào phần cứng mà thuật toán được thử nghiệm trên đó. Điều này khiến cho việc so sánh các thuật toán khó khăn nếu chúng được thử nghiệm ở những máy tính khác nhau.3 Ký pháp đánh giá thuật toán Với những lý do trên, người ta đã tìm kiếm những phương pháp đánh giá thuật toán hình thức hơn, ít phụ thuộc môi trường cũng như phần cứng hơn. Một phương pháp như vậy là phương pháp đánh giá thuật toán theo hướng xấp xỉ tiệm cận qua các khái niệm toán học O lớn O(N) (Big-O).
Thông thường các vấn đề mà chúng ta giải quyết có một "kích thước" tự nhiên (thường là số lượng dữ liệu được xử lý) mà chúng ta sẽ gọi là N. Chúng ta muốn mô tả tài nguyên cần được dùng (thông thường nhất là thời gian cần thiết để giải quyết vấn đề) như một hàm số theo N. Chúng ta quan tâm đến trường hợp trung bình, tức là thời gian cần thiết để xử lý dữ liệu nhập thông thường T (n) và cũng quan tâm đến trường hợp xấu nhất, tương ứng với thời gian cần thiết khi dữ liệu rơi vào trường hợp xấu nhất có thể có. Việc xác định chi phí trong trường hợp trung bình thường được quan tâm nhiều nhất vì nó đại diện cho đa số trường hợp sử dụng thuật toán.
Tuy nhiên, việc xác định chi phí trung bình này lại gặp nhiều khó khăn. Vì vậy, trong nhiều trường hợp, người ta xác định chi phí trong trường hợp xấu nhất (chặn trên) thay cho việc xác định chi phí trong trường hợp trung bình. Hơn nữa, trong một số bài toán, việc xác định chi phí trong trường hợp xấu nhất là rất quan trọng. Ví dụ, các bài toán trong hàng không, phẫu thuật,.
Như đã được chú ý ở trên, hầu hết các thuật toán đều có một tham số chính là N, thông thường đó là số lượng các phần tử dữ liệu được xử lý mà ảnh hưởng rất nhiều tới thời gian chạy. Tham số N có thể là bậc của một đa thức, kích thước của một tập tin được sắp xếp hay tìm kiếm, số nút trong một đồ thị,. Thông thường để đánh giá thuật toán người ta dựa trên hai tiêu chuẩn sau: • Tiêu chuẩn 1: Độ đơn giản, dễ hiểu, dễ cài đặt (viết chương trình). • Tiêu chuẩn 2: Sử dụng tiết kiệm tài nguyên hệ thống và với thời gian ngắn nhất.
Tuỳ từng trường hợp mà một trong hai tiêu chuẩn trên được quan tâm, chẳng hạn khi viết một chương trình chỉ để sử dụng một số ít lần, và thời gian để viết chương trình với thuật toán theo tiêu chuẩn 2 lại mất nhiều hơn một thuật toán khác đơn giản ngắn gọn hơn thì tiêu chuẩn 1 được chú trọng, ngược lại nếu một chương trình được sử dụng nhiều lần (chương trình con) hoặc nhiều người sử dụng. thì tiêu chuẩn 2 lại rất quan trọng. Chúng ta sẽ tìm cách đánh giá thời gian tính của thuật toán bởi một hàm của độ dài dữ liệu vào. Ta gọi kích thước dữ liệu đầu vào (hay độ dài dữ liệu vào) là số bít cần thiết để biểu diễn nó.
Phép toán cơ bản là phép toán có thể thực hiện với thời gian bị chặn bởi một hằng số không phụ thuộc vào kích thước dữ liệu. Để tính toán thời gian tính của thuật toán ta sẽ đếm 1.2 Sơ lược về phân tích, đánh giá thuật toán 19 số phép toán cơ bản mà nó phải thực hiện. Chúng ta sẽ quan tâm đến: 1. Thời gian tối thiểu cần thiết để thực hiện thuật toán với mọi bộ dữ liệu đầu vào kích thước n.
Thời gian như vậy sẽ được gọi là thời gian tính tốt nhất của thuật toán với đầu vào kích thước n. Thời gian nhiều nhất cần thiết để thực hiện thuật toán với mọi bộ dữ liệu đầu vào kích thước n. Thời gian như vậy sẽ được gọi là thời gian tính tồi nhất của thuật toán với đầu vào kích thước n. Thời gian trung bình cần thiết để thực hiện thuật toán trên tập hữu hạn các đầu vào kích thước n.
Thời gian như vậy sẽ được gọi là thời gian tính trung bình của thuật toán. Các ký hiệu tiệm cận (Asymptotic Notation) được xác định bởi các hàm nhận giá trị nguyên không âm, dùng để so sánh tốc độ tăng về thời gian tính toán của thuật toán. Cụ thể, thay vì nói chính xác, chúng ta có thể nói thời gian tính là Θ(n2 ). • Ký hiệu Θ: Đối với hàm g(n) cho trước, ta ký hiệu Θ(g(n)) là tập các hàm Θ(g(n)) = { f (n)| tồn tại các hằng số c1 , c2 và n0 sao cho 0 ≤ c1 g(n) ≤ f (n) ≤ c2 g(n) ∀n ≥ n0 }.
Để so sánh tốc độ tăng của các đa thức, cần nhìn vào số hạng với số mũ cao nhất. Chúng ta nói g(n) là cận trên tiệm cận của f (n). • Ký hiệu Ω: Đối với hàm g(n) cho trước, ta ký hiệu Ω(g(n)) là tập các hàm: Ω(g(n)) = { f (n)| tồn tại các hằng số dương c và n0 sao cho cg(n) ≤ f (n) ∀n ≥ n0 }. Chúng ta nói g(n) cận dưới tiệm cận cho f (n).10: Các tiệm cận đánh giá thời gian tính toán thuật toán Đối với hai hàm bất kỳ g(n) và f (n), f (n) = Θ(g(n)) khi và chỉ khi f (n) = O(g(n)) và f (n) = Ω(g(n)).
Tức là Θ(g(n)) = O(g(n)) ∩ Ω(g(n)) Hầu hết tất cả các thuật toán được trình bày trong giáo trình này có thời gian chạy tiệm cận tới một trong các hàm sau: • Hằng số (Constant): Đa số các lệnh trong chương trình đều được thực hiện một lần hoặc một vài lần. Nếu tất cả các lệnh trong một chương trình có tính chất này thì chúng ta nói rằng thời gian chạy của nó là hằng số. • LogN (Logarithmic): Thời gian chạy của chương trình là logarit sẽ tiến chậm khi N lớn dần. Thời gian chạy logarit xuất hiện khi chương trình được giải bằng cách chuyển về các bài toán nhỏ hơn, cắt bớt kích thước một hằng số nào đó.
Khi đó, thời gian chạy có được xem như nhỏ hơn một hằng số "lớn". Thuật toán và phân tích thuật toán • N (Linear): Là hàm tuyến tính, là trường hợp một số lượng nhỏ các xử lý được làm cho mỗi phần tử dữ liệu nhập. Khi N là một triệu thì thời gian chạy cũng cỡ như vậy. Khi N được nhân gấp đôi thì thời gian chạy cũng được nhân gấp đôi.
Đây là tình huống tối ưu cho một thuật toán mà phải xử lý N dữ liệu nhập (hay sinh ra N dữ liệu xuất). • NlogN: Thời gian chạy tăng dần với các thuật toán được giải bằng cách tách nó thành các bài toán con nhỏ hơn, sau đó giải quyết chúng một cách độc lập rồi tổ hợp các lời giải lại. Chúng ta nói rằng thời gian chạy của thuật toán như thế là "NlogN". • N 2 (Quadratic): Thời gian chạy bậc hai, trường hợp này chỉ có ý nghĩa thực tế cho các bài toán tương đối nhỏ.
Thời gian bình phương thường tăng dần lên trong các thuật toán mà xử lý tất cả các phần tử dữ liệu (có thể là hai vòng lặp lồng nhau). • N 3 (Cubic): Tương tự, thời gian chạy bậc ba của các phần tử dữ liệu có thể là 3 vòng lặp lồng nhau cũng chỉ có ý nghĩa thực tế với các bài toán nhỏ. • 2N (Exponential): Thời gian chạy lũy thừa thích hợp trong một số thuật toán thực tế. Khi N là hai mươi thì thời gian chạy là 1 triệu.
Khi N tăng gấp đôi thì thời gian chạy được nâng lên luỹ thừa hai! • N! (Factorial): Thời gian chạy giai thừa đối với các bài toán phức tạp, bùng nổ về tổ hợp. Thời gian chạy tăng lên rất nhanh khi N tăng.11: So sánh sự thay đổi các hàm tiệm cận đánh giá thuật toán Ví dụ 1. So sánh mức độ thay đổi của các hàm tiệm cận. Cơ số của logarit làm thay đổi hằng số đó nhưng không nhiều: Khi N là 1000 thì logN là 3 nếu cơ số là 10, là 10 nếu cơ số là 2; khi N là một triệu, logN được nhân gấp đôi.
bất cứ khi nào N được nhân đôi, logN tăng lên thêm một hằng số. Khi N là một triệu thì NlogN khoảng 20 triệu; khi N được nhân gấp đôi, thời gian chạy bị nhân lên nhiều hơn gấp nhiều đôi. Khi N là một ngàn thì thời gian chạy bậc hai là 1 triệu. Khi N được nhân đôi thì thời gian chạy tăng lên gấp 4 lần.
Khi N là một trăm thì thời gian chạy bậc ba là 1 triệu. Khi N được nhân đôi thì thời gian chạy tăng lên gấp 8 lần. Thời gian chạy của một chương trình cụ thể đôi khi là một hệ số hằng nhân với các số hạng nói trên ("số hạng dẫn đầu") cộng thêm một số hạng nhỏ hơn. Giá trị của hệ số hằng và các số hạng phụ thuộc vào kết quả của sự phân tích và các chi tiết cài đặt.
Hệ số của số hạng dẫn đầu liên quan tới số chỉ thị bên trong vòng lặp: Ở một tầng tùy ý của thiết kế thuật toán thì phải cẩn thận giới hạn số chỉ thị như thế. Với N lớn thì các số hạng dẫn đầu đóng vai trò chủ chốt; với N nhỏ thì các số hạng cùng đóng góp vào sự so sánh các thuật toán sẽ khó khăn hơn. Trong hầu hết các trường hợp, chúng ta sẽ gặp các chương trình có thời gian chạy là "tuyến 1.2 Sơ lược về phân tích, đánh giá thuật toán 21 tính", "NlogN", "bậc ba",. với hiểu ngầm là các phân tích hay nghiên cứu thực tế phải được làm trong trường hợp mà tính hiệu quả là rất quan trọng.