sự quan trọng của thuật toán-Nguyễn Công Trình st

Thuật toán ngẫu nhiên

Có một cách tiếp cận cho một số vấn đề là ngẫu nhiên hóa một thuật toán theo một cách nào đó. Mặc dù làm như vậy không cải thiện thuật toán trong trường hợp xấu nhất, nhưng nó thường tạo ra các thuật toán rất tốt trong trường hợp trung bình.

Quicksort là một ví dụ tốt về thuật toán thường sử dụng ngẫu nhiên. Trong trường hợp xấu nhất, quicksort sắp xếp một dãy số trong thời gian O (N ² ), trong đó N là số lượng số trong dãy. Tuy nhiên, nếu tính ngẫu nhiên được kết hợp vào một bước của Quicksort, thì khả năng trường hợp xấu nhất xảy ra gần như zero trong đời thực và về trung bình quicksort có thời gian chạy là O (N Log (N)).

Nhiều thuật toán sắp xếp khác đảm bảo thời gian chạy của O (N Log (N)), ngay cả trong trường hợp xấu nhất, nhưng chúng chậm hơn trong trường hợp trung bình ở ngoài đời thực. Các thuật toán đều có thời gian chạy ở dạng C * N Log (N) (C là hằng số với mỗi thuật toán), quicksort có hệ số C nhỏ nhất trong trường hợp trung bình, vì thế nhìn chung QuickSort là thuật toán sắp xếp nhanh nhất trong trường hợp trung bình. Do đó không lấy làm lạ khi trong Java 8, QuickSort là hàm sắp xếp mặc định của Arrays (mảng).

Một thuật toán khác sử dụng các số ngẫu nhiên là tìm trung vị của dãy số (số mà sẽ đứng ở giữa nếu dãy đó được sắp xếp) có thời gian chạy trung bình là O (N). Đây là một cải tiến đáng kể so với việc sắp xếp dãy và lấy số ở giữa, lấy O (N * Log (N)). Tất nhiên, có một vài thuật toán cụ thể (nhưng không có ngẫu nhiên hóa) tìm ra trung vị với thời gian O (N), nhưng thuật toán ngẫu nhiên thường vẫn chiến thắng về tính đơn giản và tốc độ trong trường hợp trung bình.

Nén

Một lớp thuật toán khác xử lý các tình huống như nén dữ liệu. Loại thuật toán này không có đầu ra dự kiến được ​​(như thuật toán sắp xếp), thay vào đó là cố gắng tối ưu hóa theo một số tiêu chí. Trong trường hợp nén dữ liệu, thuật toán (ví dụ LZW) cố gắng làm cho dữ liệu đầu vào bị nén còn càng ít byte càng tốt mà vẫn có thể được giải nén về dạng ban đầu.

Trong một số trường hợp, loại thuật toán này sử dụng các kỹ thuật làm cho đầu ra ở mức độ tốt nhưng không giải nén về ban đầu được, đổi lại khả năng nén cao hơn. Ví dụ, nén JPG và MP3, cả hai đều nén dữ liệu theo cách làm cho kết quả cuối cùng có chất lượng thấp hơn so với bản gốc, nhưng chúng tạo ra các tệp dung lượng nhỏ hơn nhiều, bản nén chỉ cần vẫn giữ được các yếu tố phục vụ cho thực tiễn thì vẫn được cho là tốt. Hai thuật toán này tuân theo cùng một nguyên tắc nhưng khác nhau đáng kể về chi tiết vì tính chất của chúng khác nhau (nén hình ảnh so với âm thanh).

Nguồn : engineer.beecost