Please enable JavaScript.

Coggle requires JavaScript to display documents.

Chương 8, Huỳnh Minh Ngọc - Coggle Diagram

- - - - phải kết thúc sau một số hữu hạn bước
    - - với một số dữ liệu chỉ có thể trả lại 1 kết quả duy
    - - giải thuật đơn giản dễ cài đặt ,không gây tốn bộ nhớ thực hiện nhanh
  - - - cách 2 ; dùng lưu đồ giải thuật
        
        -Sử dụng các hình khối cơ bản (Bắt đầu, Kết thúc, Khối Input, Khối Output, Khối điều kiện, Khối thao tác) và các cung để thể hiện các thao tác và trình tự thực hiện các thao tác của giải thuật
      - Cách 3:Sử dụng giả mã
      - cách 1: liệt kê từng bước bằng ngôn ngữ tự nhiên
  - - - Chia nhỏ bài toán (mô-đun chính) thành các bài toán nhỏ hơn (các mô-đun con)
    - - ngôn ngữ tự nhiên đến giả ngôn ngữ đến ngôn ngữ lập trình
  - - - thời gian thực hiện giải thuật
        
        phụ thuộc kích thước dữ liệu đàu vào bài toán
        
        không phụ thuộc máy tính và các yếu tố liên quan
        
        độ phực tạp giải thuật
        
        O(1), O(log2(n)),O(n),O(nlog2(n),O(n mũ 2),.. cấp hàm đa thức trở xuống chấp nhân được
        
        O(2 mũ n ) ,O(n!),O(n mũ n) cấp hàm mũ khó xử lý
        
        Quy tắc cộng ,nhân ,quy tắc bỏ hằng số
        
        Giải thuật T sử dụng để giải một bài toán có kích thước dữ liệu đầu vào n sẽ cần thực hiện T(n) các phép toán sơ cấp
        
        T(n) là một hàm của tham số n, là đặc trưng cho độ phức tạp tính toán của giải thuật
        
        Tổng quát: Giả sử f(n), g(n) là hai hàm số không âm, đồng biến theo n. Hàm f(n) được xác định có độ phức tạp tính toán cấp g(n), ký hiệu là O(g(n)), khi và chỉ khi tồn tại các hằng số c và n0 sao cho f(n) ≤ cg(n) khi n ≥ n0. Khi đó, ta nói f(n) có cấp g(n), ký hiệu f(n) = O(g(n)) (thực chất là cấp lớn không vượt quá g(n)
      - dụng lượng bố nhớ sử dụng
  - - - Sắp xếp chèn (insertion sort)
      - sẵp xếp nổi bọt (bubble sort)
      - Tìm kiếm nhị phân (binary searching)
      - Giải thuật đệ qui