Algorithms
Thuật toán(Algorithms) 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ó một số vấn đề cần quan tâm như sau:
1. Giới thiệu vè Algorithms
Thuật toán là các bước từng bước một để giải quyết một vấn đề mong muốn.
Ví dụ thuật toán tìm đường đi ngắn nhất, thuật toán sắp xếp mảng ..
Từ góc nhìn dữ liệu có các loại thuật toán sau:
Search - thuật toán tìm kiếm items trong dữ liệu
Sort - Thuật toán sắp xếp items
Insert - Thuật toán thêm items vào data structure
Update - Thuật toán update items trong data structure
Delete - Thuật toán xóa items tồn tại trong data structure
Các đặc điểm của thuật toán:
Unambiguous : không mơ hồ - phải xác định rõ ràng input, output và các bước dẫn đến output
Input : đầu vào của thuật toán
Output : đầu ra của thuật toán
Finiteness (tính hữu hạn): thuật toán phải kết thúc sau một số bước
Feasibility (tính khả thi): thuật toán phải khả thi với available resources
Independent (tính độc lập ): phải độc lập với các code của chương trình khác.
Một bài toán có thể nhiều cách giải khác nhau. Do đó nên chọn cách giải quyết tối ưu nhất, đây là nhiệm vụ của Algorithms.
2. Độ phức tạp của thuật toán
Độ phức tạp của thuật toán là thời gian chạy và sử dụng bộ nhớ.
2.1 Phân loại
Độ phức tạp thuật toán chia ra thành các loại sau:
Độ phức tạp về thời gian (Tn) : được tính bằng số lượng phép toán thực hiện.
Độ phức tạo về không gian (Sn): được tính bằng không gian tối đa bộ nhớ sử dụng.
Người ta ký hiệu độ phức tạp của thuật toán là O(n)
Với n là giá trị đầu vào
Độ phức tạp hằng số O(1) . Số phép tính không phụ thuộc vào đầu vào
Độ phức tạp tuyến tính O(n) . Số phép tính phụ tỉ lệ thuận với độ lớn đầu vào theo hàm số bậc nhất.
Độ phức tạp đa thức O(P(n)), với P là đa thực bậc 2 trở lên
Độ phức tạp logarit O(log n)
Độ phức tạp hàm số mũ O(2^n) : đây là độ phức tạp lớn nhất và xấu nhất.
2.2 Cách tính toán độ phức tạp
Các quy tắc:
Vòng for(int i =0;i<n ;i++) có độ phức tạp là n
Operation có độ phức tạp là 1 ví dụ: a = b + c
Quy tắc rút gọn độ phức tạp :
Tính theo bậc lớn nhất. Ví dụ: 1 + n thì độ phức tạp là n , n^2 + 7n - 3 thì độ phức tạp là n^2
Rút gọn 2n -> n
Quy tắc cộng : các dòng code chia thành từng phần độ phức tạp sẽ là tổng cộng
Quy tắc nhân : các dòng code lồng nhau độ phức tạp sẽ được nhân lên. Ví dụ một vòng lặp n độ phức tạp là n thì 2 vòng lặp lồng nhau độ phức tạp là n*n = n^2
Ví dụ: thuật toán dưới đây có độ phức tạp là : (1*n +1) * n + 1 = n^2 + n + 1 -> rút gọn ta được O(n^2) . Lưu ý ta có thể rút gọn ở chỗ thích hợp.
Tham khảo : https://learntocodetogether.com/big-oh-notation-and-time-complexity/
3. Các thuật toán sorting và searching
3.1 Các thuật toán sắp xếp
Link full : https://www.toptal.com/developers/sorting-algorithms hoặc https://sorting.at/
Về độ phức tạp của các thuật toán:
3.2 Các thuật toán tìm kiếm
4. Các thuật toán liên quan đến đồ thị
4.1 Tìm cây khung trọng số nhỏ nhất
Các thuật toán tìm cây khung có trọng số ngắn nhất:
Thuật toán Kruskal
Ví dụ :
Thuật toán Prim
Ví dụ:
4.2 Tìm đường đi ngắn nhất
Các thuật toán tìm đường đi ngắn nhất bao gồm: Dijkstra và Ford-Bellman
5. Đệ quy (Recursion)
Đệ quy là phương pháp một hàm tự gọi chính nó. Ngoài ra còn có đệ quy tương hỗ (A gọi B, B gọi A).
Đối với đệ quy chúng ta nên lưu ý 2 điều:
Điểm dừng
Gọi hàm đệ quy
Ví dụ : bài toán tháp hà nội .
Xét bài toán sau: đưa 3 cái đĩa từ cột 1 sang cột 3
Như vậy bài toán sẽ được chuyển thành như sau: + Đưa cái đĩa to nhất từ cột 1 sang cột 3 + Đưa 2 cái đĩa từ còn lại từ cột 1 sang cột 2 + Đưa nốt hai cái đĩa còn lại.
Một ví dụ khác:
Last updated
Was this helpful?