Tìm hiểu về các thuật toán cơ bản trong lập trình (Phần 1)

Chào các bạn, trong bài viết này, Codegym sẽ cùng các bạn đi tìm hiểu về các thuật toán cơ bản trong lập trình. Bắt đầu thôi!

Khái niệm về thuật toán

Thuật toán, còn gọi là giải thuật, là một tập hợp hữu hạn hay một dãy các quy tắc chặt chẽ của các chỉ thị, phương cách hay 1 trình tự các thao tác trên một đối tượng cụ thể được xác định và định nghĩa rõ ràng cho việc hoàn tất một số sự việc từ một trạng thái ban đầu cho trước; khi các chỉ thị này được áp dụng triệt để thì sẽ dẫn đến kết quả sau cùng như đã dự đoán trước.

Tính chất của thuật toán

• Tính chính xác: để đảm bảo kết quả tính toán hay các thao tác mà máy tính thực hiện được là chính xác.
• Tính rõ ràng: Thuật toán phải được thể hiện bằng các câu lệnh minh bạch; các câu lệnh được sắp xếp theo thứ tự nhất định.
• Tính khách quan: Một thuật toán dù được viết bởi nhiều người trên nhiều máy tính vẫn phải cho kết quả như nhau.
• Tính phổ dụng: Thuật toán không chỉ áp dụng cho một bài toán nhất định mà có thể áp dụng cho một lớp các bài toán có đầu vào tương tự nhau.
• Tính kết thúc: Thuật toán phải gồm một số hữu hạn các bước tính toán.

Phân tích thời gian chạy của các thuật toán cơ bản trong lập trình

Một trong những khía cạnh quan trọng nhất của thuật toán là nó nhanh như thế nào. Thường thì rất dễ dàng đưa ra một thuật toán để giải quyết vấn đề, nhưng nếu thuật toán quá chậm, thì cũng vô ích về tính hữu dụng.

Nếu tính tốc độ của thuật toán theo thời gian thực mà chúng ta đang cảm nhận. Thì tốc độ này còn bị phụ thuộc vào nơi mà thuật toán đó chạy (trên máy tính xịn, máy tính dởm) và những chi tiết khác cho việc triển khai nó (đầu vào ít hay nhiều sai sót) – Cho nên, chúng ta thường nói về thời gian chạy liên quan đến kích thước của đầu vào.

Ví dụ: Có một thuật toán, đầu vào bao gồm N số nguyên, thuật toán sẽ có thời gian chạy tỉ lệ với một hàm số của N, ví dụ N 2, khi đó thời gian chạy được gọi là tỉ lệ với N 2, được biểu thị là O (N 2 ). Điều này tức là nếu bạn dùng Java để triển khai thuật toán nói trên ở máy tính với đầu vào có kích thước N, sẽ mất C * N 2 giây, trong đó C là một hằng số không thay đổi và không liên quan gì tới N.

Tuy nhiên, thời gian thực hiện thuật toán có thể thay đổi do các yếu tố khác với kích thước của đầu vào N. Ví dụ như thuật toán sắp xếp, nếu N số nguyên đầu vào đã có xu hướng được sắp xếp trước, thì thời gian sắp xếp sẽ nhanh hơn nhiều so với việc N số đầu vào lúc đầu là ngẫu nhiên. Vì thế, chúng ta sẽ thường nghe rằng có “Thời gian chạy trường hợp xấu nhất” và “Thời gian chạy trường hợp trung bình”.

Thời gian chạy trường hợp xấu nhất là trong mọi trường hợp, N số đầu vào dường như đã ngấm ngầm được chỉ định để thuật toán không có bước nào được nghỉ ngơi. Còn Thời gian chạy trường hợp trung bình là thời gian trung bình đo được trong tất cả các đầu vào có thể. Quá trình xác định thời gian chạy trường hợp xấu nhất và trường hợp trung bình cho một thuật toán nào đó đôi khi cũng gặp khó khăn, vì thường không thể chạy thuật toán trên tất cả các đầu vào có thể hoặc không nghĩ ra được những đầu vào chống lại sự nghỉ ngơi của thuật toán. Khi gặp khó khăn trong việc này, hãy tìm kiếm tài liệu online để ước tính các giá trị đó cho thuật toán của bạn.

Đối với một máy tính hạng thường, Thời gian hoàn thành gần đúng cho các thuật toán với N = 100 như sau:

Cám ơn các bạn đã đọc, hẹn gặp lại các bạn ở phần 2 của chủ đề với phần thuật toán sắp xếp nhé.

Author: Trương Tấn Hải