Please enable JavaScript.

Coggle requires JavaScript to display documents.

CHƯƠNG 8, Nguyễn Ngọc Minh - Coggle Diagram

- - - - Dữ liệu đầu vào (Input)
      - Dữ liệu đầu ra (Output)
  - - - Có điểm bắt đầu
      - Thực hiện trong số bước hữu hạn
      - Có điểm kết thúc
    - - Mỗi bước rõ ràng
      - Không mơ hồ
      - Cùng Input → cùng Output
    - - Các bước thực hiện được
      - Cho kết quả đúng
      - Thời gian hợp lý
      - Bộ nhớ hợp lý
  - - - Mô tả các bước theo thứ tự
      - Dễ hiểu, phù hợp bài toán đơn giản
    - - Hình elip → Bắt đầu/Kết thúc
      - Hình bình hành → Nhập/Xuất dữ liệu
      - Hình chữ nhật → Xử lý/Tính toán
      - Hình thoi → Kiểm tra điều kiện
      - Mũi tên → Hướng thực hiện
    - - Gần giống ngôn ngữ lập trình
      - Không phụ thuộc ngôn ngữ cụ thể
      - Không yêu cầu cú pháp nghiêm ngặt
      - Dễ chuyển thành chương trình
  - - - Mô tả bằng lời
    - - Mô tả các bước xử lý
    - - Python
      - C++
      - Java
    - - Ngôn ngữ tự nhiên
      - → Giả ngôn ngữ
      - → Ngôn ngữ lập trình
  - - - Phụ thuộc kích thước dữ liệu đầu vào
      - Kích thước dữ liệu ký hiệu là n
      - Dựa vào số lượng thao tác
      - Xem tốc độ tăng khi n tăng
    - - Lưu biến
      - Lưu dữ liệu
      - Lưu kết quả
      - Lưu dữ liệu trung gian
  - - - T: thời gian hoặc số thao tác
      - O: tốc độ tăng theo kích thước n
    - - Độ phức tạp hằng số
      - Số thao tác không đổi
    - - Mỗi lần giảm dữ liệu còn một nửa
    - - Một vòng lặp chạy n lần
    - - n lần × log₂n lần
    - - Hai vòng lặp lồng nhau
      - n × n = n²
    - - Tăng rất nhanh
    - - Tăng cực nhanh
    - - Tăng rất lớn
    - - O(1)
      - O(log₂n)
      - O(n)
      - O(nlog₂n)
      - O(n²)
      - O(2ⁿ)
      - O(n!)
      - O(nⁿ)
  - - - Các đoạn lệnh thực hiện nối tiếp
    - - Cộng độ phức tạp các đoạn
      - Giữ bậc tăng nhanh nhất
    - - n + n² → O(n²)
  - - - Các vòng lặp hoặc công việc lồng nhau
    - - Nhân số lần thực hiện
    - - n × n → O(n²)
      - n × log₂n → O(nlog₂n)
  - - - 5n → O(n)
      - 100n² → O(n²)
      - 2n² + 5n + 10 → O(n²)