Tại sao cần phải phân tích hiệu suất ?
Có rất nhiều điều quan trọng cần được quan tâm, như tính thân thiện với người dùng, tính mô-đun, bảo mật, khả năng bảo trì, v.v. Tại sao phải lo lắng về hiệu suất?
Câu trả lời cho điều này rất đơn giản, chúng ta có thể có tất cả những điều trên chỉ khi chúng ta có hiệu suất. Vì vậy, hiệu suất giống như tiền tệ mà thông qua đó chúng ta có thể mua tất cả những thứ trên. Một lý do khác để nghiên cứu hiệu suất là:
Tốc độ là Niềm vui!
Tóm lại, hiệu suất == thang đo. Hãy tưởng tượng một trình soạn thảo văn bản có thể tải 1000 trang, nhưng có thể kiểm tra chính tả 1 trang mỗi phút HOẶC một trình chỉnh sửa hình ảnh mất 1 giờ để xoay hình ảnh của bạn sang trái 90 độ HOẶC… bạn hiểu rồi. Nếu một tính năng phần mềm không thể đáp ứng được quy mô nhiệm vụ mà người dùng cần thực hiện - thì điều đó coi như đã chết.
Đưa ra hai thuật toán cho một nhiệm vụ, làm cách nào để chúng ta tìm ra thuật toán nào tốt hơn?
Một cách đơn giản để làm điều này là - thực hiện cả hai thuật toán và chạy hai chương trình trên máy tính của bạn cho các đầu vào khác nhau và xem chương trình nào tốn ít thời gian hơn. Có rất nhiều vấn đề với cách tiếp cận này để phân tích các thuật toán.
1) Có thể đối với một số đầu vào, thuật toán đầu tiên hoạt động tốt hơn thuật toán thứ hai. Và đối với một số đầu vào thứ hai hoạt động tốt hơn.
2) Cũng có thể đối với một số đầu vào, thuật toán đầu tiên hoạt động tốt hơn trên một máy và thuật toán thứ hai hoạt động tốt hơn trên máy khác đối với một số đầu vào khác.
Phân tích tiệm cận là ý tưởng lớn xử lý các vấn đề trên trong phân tích thuật toán. Trong Phân tích tiệm cận, chúng tôi đánh giá hiệu suất của một thuật toán về kích thước đầu vào (chúng tôi không đo thời gian chạy thực tế). Chúng tôi tính toán, thời gian (hoặc không gian) được sử dụng bởi một thuật toán sẽ tăng lên như thế nào với kích thước đầu vào.
Ví dụ, chúng ta hãy xem xét vấn đề tìm kiếm (tìm kiếm một mục nhất định) trong một mảng được sắp xếp. Một cách để tìm kiếm là Tìm kiếm tuyến tính (thứ tự tăng trưởng là tuyến tính) và cách khác là Tìm kiếm nhị phân (thứ tự tăng trưởng là logarit).
Để hiểu cách Phân tích tiệm cận giải quyết các vấn đề được đề cập ở trên trong phân tích thuật toán, giả sử chúng ta chạy Tìm kiếm tuyến tính trên máy tính nhanh A và Tìm kiếm nhị phân trên máy tính chậm B.và chúng tôi chọn các giá trị không đổi cho hai máy tính để nó cho chúng tôi biết chính xác thời gian để máy tính đó thực hiện tìm kiếm trong vài giây.
Giả sử hằng số của A là 0,2 và hằng số của B là 1000, có nghĩa là A mạnh hơn gấp 5000 lần so với B. Đối với các giá trị nhỏ của kích thước mảng đầu vào n, máy tính nhanh có thể mất ít thời gian hơn.
Tuy nhiên, sau một giá trị nhất định của kích thước mảng đầu vào, Tìm kiếm nhị phân chắc chắn sẽ bắt đầu mất ít thời gian hơn so với Tìm kiếm tuyến tính mặc dù Tìm kiếm nhị phân đang được chạy trên máy chậm.
Lý do là thứ tự tăng trưởng của Tìm kiếm nhị phân đối với kích thước đầu vào là logarit trong khi thứ tự tăng trưởng của Tìm kiếm tuyến tính là tuyến tính. Vì vậy, các hằng số phụ thuộc máy luôn có thể bị bỏ qua sau một giá trị nhất định của kích thước đầu vào.
Dưới đây là một số thời gian chạy cho ví dụ này:
Thời gian chạy Tìm kiếm tuyến tính tính bằng giây trên A : 0.2 * n
Thời gian chạy Tìm kiếm nhị phân tính bằng giây trên B : 1000 * log (n)
------------------------------------------------
|n | Running time on A | Running time on B |
-------------------------------------------------
|10 | 2 sec | ~ 1 h |
-------------------------------------------------
|100 | 20 sec | ~ 1.8 h |
-------------------------------------------------
|10^6 | ~ 55.5 h | ~ 5.5 h |
-------------------------------------------------
|10^9 | ~ 6.3 years | ~ 8.3 h |
-------------------------------------------------
Phân tích tiệm cận có luôn hoạt động không?
Phân tích tiệm cận không phải là hoàn hảo, nhưng đó là cách tốt nhất hiện có để phân tích các thuật toán. Ví dụ: giả sử có hai thuật toán sắp xếp mất 1000nLogn và 2nLogn thời gian tương ứng trên một máy. Cả hai thuật toán này đều tiệm cận giống nhau (thứ tự tăng trưởng là nLogn). Vì vậy, với Phân tích tiệm cận, chúng ta không thể đánh giá cái nào tốt hơn khi chúng ta bỏ qua các hằng số trong Phân tích tiệm cận.
Ngoài ra, trong phân tích tiệm cận, chúng ta luôn nói về kích thước đầu vào lớn hơn một giá trị không đổi. Có thể những đầu vào lớn đó không bao giờ được cấp cho phần mềm của bạn và một thuật toán tiệm cận chậm hơn, luôn hoạt động tốt hơn cho tình huống cụ thể của bạn. Vì vậy, cuối cùng bạn có thể chọn một thuật toán tiệm cận chậm hơn nhưng nhanh hơn cho phần mềm của bạn.
Bài viết thuộc loạt bài
Cấu Trúc Dữ Liệu và Giải Thuật
Đăng nhận xét