Xem trước tài liệu

Đang tải tài liệu...

Thông tin chi tiết tài liệu

Định dạng: DOC
Số trang: 25 trang
Dung lượng: 761 KB

Giới thiệu nội dung

Nền Tảng Lý Thuyết Và Phân Tích Độ Phức Tạp Của Các Thuật Toán Sắp Xếp

Lĩnh vực: Khoa học máy tính, Thuật toán

Nội dung tài liệu:

Tài liệu này trình bày nền tảng lý thuyết về các thuật toán sắp xếp, tập trung phân tích hai thuật toán chính là Sắp xếp bằng phương pháp chèn (Insertion Sort) và Sắp xếp nhanh (Quick Sort). Mục tiêu là mô tả chức năng, yêu cầu, phân tích và đánh giá độ phức tạp của chúng cả về mặt lý thuyết lẫn thực nghiệm. Tài liệu cũng đề cập đến việc cài đặt các thuật toán này bằng ngôn ngữ lập trình C/C++ và cách đánh giá hiệu quả dựa trên việc chọn giá trị mốc.

Mục lục chi tiết:

  • Phần A: Nền tảng lý thuyết
    • Mô tả chức năng và yêu cầu
    • Khái quát về sắp xếp
    • Phân tích, đánh giá và so sánh độ phức tạp (lý thuyết) và thời gian tính toán (thực nghiệm) của 2 giải thuật
    • Đánh giá độ phức tạp của giải thuật Sắp xếp bằng phương pháp chèn (Insertion Sort)
      • Ý tưởng thuật toán
      • Đánh giá độ phức tạp
    • Đánh giá độ phức tạp của giải thuật Sắp xếp nhanh (Quick Sort)
      • Ý tưởng thuật toán
      • Độ phức tạp của thuật toán
      • Trường hợp tốt nhất, xấu nhất, trung bình
  • Phần B: Thực nghiệm
    • Mô tả giải thuật
    • Cài đặt và đánh giá độ phức tạp