Please enable JavaScript.

Coggle requires JavaScript to display documents.

Chương 8: GIẢI THUẬT - Coggle Diagram

- - - - Dừng sau một số hữu hạn bước
    - - Các bước rõ ràng, không nhập nhằng
      - Cùng Input chỉ cho 1 Output duy nhất
    - - Cài đặt đơn giản, chạy nhanh, tiết kiệm bộ nhớ
  - - - Liệt kê từng bước bằng văn bản
    - - Khối Elip
        
        Bắt đầu / Kết thúc
      - Khối Chữ nhật
        
        Thao tác xử lý / Phép gán
      - Khối Thoi
        
        Điều kiện rẽ nhánh (+ / -)
      - Khối BÌnh hành
        
        Nhập Input / Xuất Output
    - - Kết hợp cấu trúc lập trình và ngôn ngữ tự nhiên
  - - - Chia bài toán lớn thành các bài toán con
    - - Ngôn ngữ tự nhiên -> Giả ngôn ngữ -> Ngôn ngữ lập trình
  - - - Thời gian thực hiện (Time Complexity)
      - Dung lượng bộ nhớ (Space Complexity)
    - - Đánh giá theo kích thước dữ liệu đầu vào n
      - Thứ tự độ phức tạp tăng dần
        
        O(1) - Hằng số
        
        O(log n) - Logarit
        
        O(n) - Tuyến tính
        
        O(n log n) - N log N
        
        O(n^2), O(n^3) - Đa thức
        
        O(2^n), O(n!), O(n^n) - Cấp số mũ (rất chậm)
    - - Quy tắc cộng
        
        O(f(n)) + O(g(g)) = O(max(f(n), g(n)))
      - Quy tắc nhân
        
        O(f(n)) O(g(n)) = O(f(n) g(n))
      - Quy tắc bỏ hằng số
        
        O(c * f(n)) = O(f(n))
  - - - Sắp xếp Lựa chọn (Selection Sort)
        
        Tìm phần tử nhỏ nhất và đổi chỗ về vị trí đầu
      - Sắp xếp Chèn (Insertion Sort)
        
        Chèn phần tử hiện tại vào vị trí đúng trong dãy đã sắp
      - Sắp xếp Nổi bọt (Bubble Sort)
        
        So sánh đổi chỗ các cặp kề nhau từ phải sang trái
    - - Tìm kiếm Tuần tự (Sequential Search)
        
        Duyệt từng phần tử từ đầu đến cuối dãy
      - Tìm kiếm Nhị phân (Binary Search)
        
        Yêu cầu dãy đã sắp xếp
        
        Chia đôi khoảng tìm kiếm dựa trên phần tử ở giữa
    - - Khái niệm
        
        Hàm / thủ tục tự gọi lại chính nó
      - Thành phần bắt buộc
        
        Trường hợp suy biến (Điểm dừng)
        
        Phần đệ quy (Qui nạp)
      - Ví dụ kinh điển
        
        Tính giai thừa n!
        
        Bài toán Tháp Hà Nội
- - - - Xác định dữ liệu Input và Output
    - - Tìm cách xử lý dữ liệu đầu vào
    - - Viết bằng ngôn ngữ lập trình
    - - Biên dịch chương trình sang mã máy
    - - Máy tính xử lý dữ liệu và trả kết quả Output