Tiếp theo bài trước, bài này chúng ta sẽ tìm hiểu sâu và chi tiết hơn về các đặc điểm, thuật ngữ liên quan tới thuật toán(Algorithms), nhằm giúp ace dễ dàng tìm hiểu và học các thuật toán sau này nhanh hơn.
Nội dung chính
1. Giới thiệu về thuật toán
Thuật toán là một thủ tục từng bước, xác định một tập hợp các lệnh được thực hiện theo một thứ tự nhất định để có được đầu ra mong muốn. Các thuật toán thường được tạo độc lập với các ngôn ngữ cơ bản, tức là một thuật toán có thể được triển khai bằng nhiều ngôn ngữ lập trình.
Từ quan điểm cấu trúc dữ liệu, sau đây là một số loại thuật toán quan trọng:
- Tìm kiếm(Search) – Thuật toán tìm kiếm một mục(phần tử) trong cấu trúc dữ liệu.
- Sắp xếp(Sort) – Thuật toán sắp xếp các mục theo một thứ tự nhất định.
- Chèn(Insert) – Thuật toán chèn mục trong cấu trúc dữ liệu.
- Cập nhật(Update) – Thuật toán cập nhật một mục hiện có trong cấu trúc dữ liệu.
- Xóa(Delete) – Thuật toán xóa một mục hiện có khỏi cấu trúc dữ liệu.
2. Các đặc điểm nhận biết thuật toán
Không phải tất cả các thủ tục đều có thể được gọi là một thuật toán. Thuật toán phải có các đặc điểm sau:
- Rõ ràng(Unambiguous) – Thuật toán phải rõ ràng và rõ ràng. Mỗi bước (hoặc giai đoạn) của nó, và đầu vào / đầu ra của chúng phải rõ ràng và chỉ dẫn đến một ý nghĩa.
- Đầu vào(Input) – Một thuật toán phải có 0 hoặc nhiều đầu vào được xác định rõ.
- Đầu ra(Output) – Một thuật toán phải có 1 hoặc nhiều đầu ra được xác định rõ ràng và phải phù hợp với đầu ra mong muốn.
- Tính hữu hạn(Finiteness) – Thuật toán phải kết thúc sau một số bước hữu hạn.
- Tính khả thi(Feasibility) – Phải khả thi với các nguồn lực sẵn có(tài nguyên, thiết bị hiện có).
- Độc lập(Independent) – Một thuật toán nên có hướng dẫn từng bước, điều này phải độc lập với bất kỳ code lập trình nào.
3. Cách viết thuật toán
Không có tiêu chuẩn được xác định rõ ràng để viết thuật toán. Đúng hơn, đó là vấn đề và phụ thuộc vào tài nguyên. Các thuật toán không bao giờ được viết để hỗ trợ một code lập trình cụ thể.
Như chúng ta biết rằng tất cả các ngôn ngữ lập trình đều có chung các cấu trúc code cơ bản như vòng lặp (do, for, while), điều khiển luồng (if-else), v.v. Những cấu trúc chung này có thể được sử dụng để viết một thuật toán.
Chúng ta viết các thuật toán theo cách thức từng bước, nhưng không phải lúc nào cũng vậy. Viết thuật toán là một quá trình và được thực hiện sau khi miền vấn đề được xác định rõ. Đó là, chúng ta nên biết miền vấn đề mà chúng ta đang thiết kế một giải pháp cho nó.
Thí dụ
Hãy thử tìm hiểu cách viết thuật toán bằng cách sử dụng một ví dụ.
Bài toán – Thiết kế một thuật toán để cộng hai số và hiển thị kết quả.
Phương pháp mô tả 1:
Bước 1 – BẮT ĐẦU
Bước 2 – khai báo ba số nguyên a, b & c
Bước 3 – xác định các giá trị của a & b
Bước 4 – thêm các giá trị của a & b
Bước 5 – lưu trữ đầu ra của bước 4 đến c
Bước 6 – in c
Bước 7 – DỪNG
Các thuật toán cho người lập trình biết cách viết code chương trình. Ngoài ra, thuật toán có thể được viết dưới dạng:
Phương pháp mô tả 2:
Bước 1 – BẮT ĐẦU THÊM
Bước 2 – nhận các giá trị của a & b
Bước 3 – c ← a + b
Bước 4 – hiển thị c
Bước 5 – DỪNG
Trong thiết kế và phân tích các thuật toán, thường thì phương pháp thứ hai được sử dụng để mô tả một thuật toán. Nó giúp nhà phân tích dễ dàng phân tích thuật toán bỏ qua tất cả các định nghĩa không mong muốn. Anh ta có thể quan sát những thao tác nào đang được sử dụng và quy trình đang diễn ra như thế nào.
Viết số bước, là tùy chọn.
Chúng ta thiết kế một thuật toán để có được giải pháp của một vấn đề nhất định. Một vấn đề có thể được giải quyết bằng nhiều cách
Do đó, nhiều thuật toán giải pháp có thể được rút ra cho một vấn đề nhất định. Bước tiếp theo là phân tích các thuật toán giải pháp được đề xuất đó và triển khai giải pháp phù hợp nhất.
4. Phân tích thuật toán
Hiệu quả của một thuật toán có thể được phân tích ở hai giai đoạn khác nhau, trước khi thực hiện và sau khi thực hiện. Chúng là những thứ sau –
- Phân tích đầu tiên – Đây là phân tích lý thuyết về một thuật toán. Hiệu quả của một thuật toán được đo lường bằng cách giả định rằng tất cả các yếu tố khác, ví dụ, tốc độ bộ xử lý, là không đổi và không ảnh hưởng đến việc triển khai.
- Phân tích sau- Đây là một phân tích thực nghiệm của một thuật toán. Thuật toán đã chọn được thực hiện bằng ngôn ngữ lập trình. Điều này sau đó được thực hiện trên máy tính đích. Trong phân tích này, số liệu thống kê thực tế như thời gian chạy và không gian cần thiết, được thu thập.
Chúng ta sẽ tìm hiểu về phân tích thuật toán. Phân tích thuật toán đề cập đến việc thực thi hoặc thời gian chạy của các hành động khác nhau có liên quan. Thời gian chạy của một thao tác có thể được định nghĩa là số lượng lệnh máy tính được thực hiện trên mỗi thao tác.
5. Độ phức tạp của thuật toán
Giả sử X là một thuật toán và n là kích thước của dữ liệu đầu vào, thời gian và không gian mà thuật toán X sử dụng là hai yếu tố chính, quyết định hiệu quả của X.
- Yếu tố thời gian(Time Factor) – Thời gian được đo bằng cách đếm số lượng các thao tác chính như việc so sánh trong thuật toán sắp xếp.
- Hệ số không gian(Space Factor) – Không gian được đo bằng cách đếm không gian bộ nhớ tối đa mà thuật toán yêu cầu.
Độ phức tạp của thuật toán f (n) cung cấp thời gian chạy và / hoặc không gian lưu trữ mà thuật toán yêu cầu theo n là kích thước của dữ liệu đầu vào.
5.1 Độ phức tạp về thời gian
Độ phức tạp thời gian của một thuật toán biểu thị lượng thời gian mà thuật toán yêu cầu để chạy đến khi hoàn thành. Yêu cầu về thời gian có thể được định nghĩa như một hàm số T (n), trong đó T (n) có thể được đo bằng số bước, miễn là mỗi bước tiêu thụ thời gian không đổi.
Ví dụ, phép cộng hai số nguyên n bit thực hiện n bước. Do đó, tổng thời gian tính toán là T (n) = c ∗ n, trong đó c là thời gian thực hiện phép cộng hai bit. Ở đây, chúng ta quan sát thấy rằng T (n) tăng tuyến tính khi kích thước đầu vào tăng lên.
5.2 Độ phức tạp về không gian
Độ phức tạp không gian của một thuật toán biểu thị lượng không gian bộ nhớ mà thuật toán yêu cầu trong vòng đời của nó. Không gian được yêu cầu bởi một thuật toán bằng tổng của hai thành phần sau:
- Một phần cố định là không gian cần thiết để lưu trữ dữ liệu và biến nhất định, độc lập với quy mô của vấn đề. Ví dụ, các biến và hằng số đơn giản được sử dụng, kích thước chương trình, v.v.
- Một phần biến là một không gian được yêu cầu bởi các biến, kích thước của nó phụ thuộc vào kích thước của bài toán. Ví dụ, cấp phát bộ nhớ động, không gian ngăn xếp đệ quy, v.v.
Độ phức tạp không gian S (P) của bất kỳ thuật toán P nào là S (P) = C + SP (I), trong đó C là phần cố định và S (I) là phần biến của thuật toán, phụ thuộc vào đặc tính cá thể I. Sau đây là một ví dụ đơn giản cố gắng giải thích khái niệm –
Thuật toán: SUM (A, B)
Bước 1 – BẮT ĐẦU
Bước 2 – C ← A + B + 10
Bước 3 – Dừng lại
Ở đây chúng ta có ba biến A, B, C và một hằng số. Do đó S (P) = 1 + 3. Bây giờ, không gian phụ thuộc vào kiểu dữ liệu của các biến và kiểu hằng đã cho và nó sẽ được nhân lên tương ứng.
Nguồn và Tài liệu tiếng anh tham khảo:
Tài liệu từ cafedev:
- Full series tự học Cấu trúc dữ liệu và giải thuật từ cơ bản tới nâng cao tại đây nha.
- Ebook về Cấu trúc dữ liệu và giải thuật tại đây.
- Các series tự học lập trình khác
Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:
Chào thân ái và quyết thắng!
, nhằm giúp ace dễ dàng tìm hiểu và học các thuật toán sau này nhanh hơn.){kind=link}