Bài tập — Bài 24: Đánh giá độ phức tạp thời gian thuật toán

Phần 1: Câu hỏi Trắc nghiệm (Nhận biết & Thông hiểu)

Câu 1. Nội dung nào sau đây phản ánh đúng kiến thức cần ghi nhớ trong bài Bài 24: Đánh giá độ phức tạp thời gian thuật toán? A. Bỏ qua các khái niệm cơ bản và chỉ học thuộc lòng kết quả cuối cùng mà không cần hiểu bản chất. B. Chỉ áp dụng kiến thức trong một trường hợp duy nhất, không cần kiểm tra điều kiện hay đơn vị. C. Các nội dung trong bài hoàn toàn độc lập và không có mối liên hệ nào với thực tiễn hay các bài học khác. D. Độ phức tạp thời gian cho biết thời gian chạy tăng như thế nào khi kích thước dữ liệu tăng.

Câu 2. Khi học và vận dụng bài Bài 24: Đánh giá độ phức tạp thời gian thuật toán, khẳng định nào dưới đây là chính xác? A. Kí hiệu O lớn mô tả tốc độ tăng trưởng: O(1), O(log n), O(n), O(n^2). B. Không cần đọc kĩ đề bài hay phân tích dữ kiện trước khi thực hiện các bước giải. C. Mọi khái niệm trong bài đều có thể thay thế tùy ý cho nhau mà không làm thay đổi kết quả. D. Chỉ cần ghi đáp số ngắn gọn, bỏ qua toàn bộ bước lập luận, giải thích và kiểm tra lại.

Câu 3. Theo phần Kiến thức trọng tâm của bài Bài 24: Đánh giá độ phức tạp thời gian thuật toán, phát biểu nào sau đây là đúng? A. Kết luận ngay kết quả khi chưa đối chiếu với quy tắc hoặc định nghĩa trong bài học. B. Độ phức tạp thời gian cho biết thời gian chạy của thuật toán tăng lên như thế nào khi kích thước dữ liệu đầu vào tăng lên. C. Thay đổi toàn bộ quy tắc trọng tâm của bài học theo cảm tính cá nhân. D. Bỏ qua việc rèn luyện qua ví dụ minh họa và bài tập thực hành của tiết học.

Câu 4. Để nắm vững và vận dụng tốt bài Bài 24: Đánh giá độ phức tạp thời gian thuật toán, học sinh cần lưu ý điều nào sau đây? A. Không cần ghi nhớ các lưu ý trọng tâm vì chúng không ảnh hưởng đến việc làm bài tập. B. Áp dụng ngược lại hoàn toàn so với quy tắc và hướng dẫn trong phần kiến thức trọng tâm. C. Hai thuật toán cho cùng kết quả có thể chênh lệch thời gian chạy rất lớn. D. Chỉ cần đọc lướt tiêu đề bài học mà không cần nắm vững nội dung chi tiết từng mục.

Phần 2: Bài tập Tự luận & Thực hành theo tiết học

Bài 1 (Cơ bản — Hệ thống hóa kiến thức trọng tâm). Dựa vào phần Kiến thức trọng tâm của bài Bài 24: Đánh giá độ phức tạp thời gian thuật toán, em hãy trình bày các khái niệm, quy tắc hoặc nội dung cốt lõi của tiết học và nêu ý nghĩa của chúng.

Bài 2 (Thực hành — Phân tích & Giải mẫu theo ví dụ tiết học). Đọc kĩ tình huống/ví dụ trọng tâm của tiết học dưới đây, sau đó tự trình bày lại các bước thực hiện và nêu nhận xét rút ra:

Ví dụ: so sánh hai thuật toán tìm kiếm trên dãy có n = 1 000 000 phần tử. Với tìm kiếm tuần tự, trường hợp xấu nhất phải duyệt hết cả triệu phần tử, tức khoảng 1 000 000 lần so sánh. Với tìm kiếm nhị phân, mỗi bước loại bỏ một nửa khoảng tìm kiếm, nên sau khoảng log2(1 000 000) ≈ 20 lần so sánh là tìm ra đáp án. Nếu mỗi lần so sánh mất một phần triệu giây, tìm kiếm tuần tự mất khoảng một giây, tìm kiếm nhị phân chỉ mất khoảng hai mươi phần triệu giây. Vì vậy, chọn thuật toán có độ phức tạp thấp rất quan trọng khi dữ liệu lớn.

Bài 3 (Vận dụng — Áp dụng quy tắc ghi nhớ vào bài tập). Vận dụng các điểm ghi nhớ trọng tâm của bài Bài 24: Đánh giá độ phức tạp thời gian thuật toán để giải thích hoặc thực hiện yêu cầu thực hành mở rộng sau:

Sắp xếp nổi bọt và sắp xếp chọn đều có độ phức tạp O(n^2) trong trường hợp xấu nhất, nghĩa là khi n tăng gấp đôi, thời gian chạy tăng khoảng bốn lần.

Bài 4 (Luyện tập học kì — Mức độ Cơ bản). Cho bảng Lop(MaLop, TenLop). Hãy viết câu lệnh SQL liệt kê tất cả các lớp.

Bài 5 (Luyện tập học kì — Mức độ Thông hiểu). Nêu một ví dụ về khóa ngoại trong đời sống quản lí (ví dụ: bảng điểm tham chiếu tới bảng học sinh) và giải thích.

Bài 6 (Luyện tập học kì — Mức độ Vận dụng & Nâng cao). Viết đoạn chương trình Python đếm số phần tử lớn hơn 5 trong mảng [3, 8, 1, 9, 4].

Phần 3: Đáp án & Hướng dẫn giải chi tiết

1. Đáp án phần Trắc nghiệm

• Bảng đáp án: 1-D, 2-A, 3-B, 4-C.
• Giải thích chi tiết:
  • Câu 1 (D): Khẳng định đúng theo mục Ghi nhớ của bài: "Độ phức tạp thời gian cho biết thời gian chạy tăng như thế nào khi kích thước dữ liệu tăng."
  • Câu 2 (A): Khẳng định đúng theo nội dung cốt lõi của tiết học: "Kí hiệu O lớn mô tả tốc độ tăng trưởng: O(1), O(log n), O(n), O(n^2)."
  • Câu 3 (B): Khẳng định chuẩn xác theo phần Kiến thức trọng tâm: "Độ phức tạp thời gian cho biết thời gian chạy của thuật toán tăng lên như thế nào khi kích thước dữ liệu đầu vào tăng lên."
  • Câu 4 (C): Khẳng định đúng theo hướng dẫn trọng tâm của bài: "Hai thuật toán cho cùng kết quả có thể chênh lệch thời gian chạy rất lớn."

2. Hướng dẫn giải phần Tự luận & Thực hành

• Bài 1:
  • Nội dung cốt lõi cần trình bày: Độ phức tạp thời gian cho biết thời gian chạy của thuật toán tăng lên như thế nào khi kích thước dữ liệu đầu vào tăng lên. Đánh giá độ phức tạp giúp so sánh và lựa chọn thuật toán phù hợp, đặc biệt khi xử lí dữ liệu lớn.
  • Tổng kết ghi nhớ: Độ phức tạp thời gian cho biết thời gian chạy tăng như thế nào khi kích thước dữ liệu tăng.; Kí hiệu O lớn mô tả tốc độ tăng trưởng: O(1), O(log n), O(n), O(n^2).; Thường đánh giá theo trường hợp xấu nhất để có giới hạn an toàn về thời gian.
• Bài 2:
  • Hướng dẫn phân tích & trình bày: Dựa trực tiếp vào dữ kiện trong ví dụ minh họa của tiết học: Ví dụ: so sánh hai thuật toán tìm kiếm trên dãy có n = 1 000 000 phần tử. Với tìm kiếm tuần tự, trường hợp xấu nhất phải duyệt hết cả triệu phần tử, tức khoảng 1 000 000 lần so sánh. Với tìm kiếm nhị phân, mỗi bước loại bỏ một nửa khoảng tìm kiếm, nên sau khoảng log2(1 000 000) ≈ 20 lần so sánh là tìm ra đáp án. Nếu mỗi lần so sánh mất một phần triệu giây, tìm kiếm tuần tự mất khoảng một giây, tìm kiếm nhị phân chỉ mất khoảng hai mươi phần triệu giây. Vì vậy, chọn thuật toán có độ phức tạp thấp rất quan trọng khi dữ liệu lớn.
  • Lưu ý khi trình bày: Xác định rõ yêu cầu, áp dụng đúng quy tắc/khái niệm trong mục 1 và kiểm tra lại kết quả cuối cùng.
• Bài 3:
  • Phương pháp giải: Áp dụng các quy tắc ghi nhớ của bài Bài 24: Đánh giá độ phức tạp thời gian thuật toán (Độ phức tạp thời gian cho biết thời gian chạy tăng như thế nào khi kích thước dữ liệu tăng.; Kí hiệu O lớn mô tả tốc độ tăng trưởng: O(1), O(log n), O(n), O(n^2).; Thường đánh giá theo trường hợp xấu nhất để có giới hạn an toàn về thời gian.).
  • Lời giải mẫu/Nhận xét: Sắp xếp nổi bọt và sắp xếp chọn đều có độ phức tạp O(n^2) trong trường hợp xấu nhất, nghĩa là khi n tăng gấp đôi, thời gian chạy tăng khoảng bốn lần.
• Bài 4: SELECT * FROM Lop;
• Bài 5: Ví dụ: bảng Diem có trường MaHS tham chiếu tới MaHS của bảng HocSinh, đảm bảo mỗi điểm thuộc về một học sinh đã tồn tại.
• Bài 6: python a = [3, 8, 1, 9, 4] dem = 0 for x in a: if x > 5: dem += 1 print(dem) # 2