Soạn giáo án điện tử khoa học máy tính 11 KNTT Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Nội dung giáo án

NHIỆT LIỆT CHÀO MỪNG CẢ LỚP ĐẾN VỚI TIẾT HỌC MỚI!

KHỞI ĐỘNG

Các quy tắc đơn giản tính độ phức tạp thời gian mang lại cho em điều gì khi đánh giá thuật toán?

Đánh giá được mức đơn giản của thuật toán, từ đó tìm ra cách giải nhanh nhất.

BÀI 25: THỰC HÀNH XÁC ĐỊNH ĐỘ PHỨC TẠP THỜI GIAN CỦA THUẬT TOÁN

NỘI DUNG THỰC HÀNH

Nhiệm vụ 1

Xác định độ phức tạp thời gian tính toán của thuật toán tìm kiếm tuần tự được thể hiện bằng chương trình sau:

Hướng dẫn:

Bước 1. Phân tích thời gian tính toán của thuật toán.

• Gọi n là kích thước của mảng đầu vào, T(n) là thời gian thực hiện thuật toán.
• Đối với mã lệnh trên, chương trình sẽ thực hiện duyệt mảng và với mỗi bước lặp sẽ kiểm tra phần tử thứ i có bằng với phần tử cần tìm kiếm không (dòng 3). Nếu bằng thì chương trình sẽ trả về chỉ số của phần tử tìm thấy và kết thúc (dòng 4).
• Lệnh trả về sẽ được thực hiện duy nhất một lần ở dòng 4 (trường hợp tìm thấy phần tử trong mảng) hoặc dòng 5 (trường hợp không tìm thấy phần tử trong mảng) → mất 1 đơn vị thời gian.
• Do đó, tổng số phép tính cơ bản của chương trình trong trường hợp tồi nhất là: T(n) = n + 1.

Bước 2. Xác định độ phức tạp O-lớn của thuật toán:

T(n) = n + 1 = O(n + 1) = O(max(n, 1)) = O(n)

Vậy thuật toán tìm kiếm tuần tự có độ phức tạp tuyến tính.

Nhiệm vụ 2

Xác định độ phức tạp của thuật toán sắp xếp chọn được thể hiện bằng chương trình sau:

Hướng dẫn:

Bước 1. Phân tích thời gian tính toán của thuật toán.

Gọi n là kích thước của mảng A, T(n) là thời gian chạy của thuật toán. Thời gian chạy của thuật toán được phân tích như sau:

• Lệnh gán ở dòng 2 tốn 1 đơn vị thời gian.
• Vòng lặp tại dòng 3 biến i sẽ chạy từ 0 đến n - 2, vậy vòng lặp này có n - 1 bước lặp.
• Tại mỗi bước lặp của lệnh for tại dòng 3 chương trình sẽ thực hiện các lệnh sau:
  • Lệnh gán tại dòng 4 tốn 1 đơn vị thời gian.
  • Vòng lặp for tại dòng 5, biến j sẽ chạy từ i + 1 đến n – 1, nên vòng lặp này có n – i – 1 bước lặp.Với mỗi bước lặp tại dòng 5 chương trình sẽ thực hiện:
  • 1 lệnh so sánh tại dòng 6 tốn 1 đơn vị thời gian và 1 lệnh gán tại dòng 7 tốn 1 đơn vị thời gian (nếu điều kiện thỏa mãn).

     → Mỗi bước lặp tại dòng 5 sẽ tốn tối đa 2 đơn vị thời gian.

• 1 lệnh đổi chỗ tại dòng 8 tốn 3 đơn vị thời gian.

Tổng hợp lại, ta thấy thời gian chạy chương trình trên là:

Bước 2. Xác định độ phức tạp O-lớn của thuật toán:

T(n) = O(max(n², 3n, –3)) = O(n²)

Vậy thuật toán sắp xếp chọn có độ phức tạp thời gian bình phương.

LUYỆN TẬP

Bài 1 (SGK - tr.117): Xác định độ phức tạp của thuật toán sắp xếp nổi bọt sau:

          def BubbleSort(A):

              n = len(A)

              for i in range(n-1):

                   for j in range(n-1-i):

                       if A[j] > A[j+1]:

                             A[j],A[j+1] = A[j+1],A[j]

Hướng dẫn:

Bước 1. Phân tích thời gian tính toán của thuật toán.

Gọi n là kích thước của mảng, T(n) là thời gian thực hiện của thuật toán. Thời gian chạy của thuật toán được phân tích như sau:

• Câu lệnh tại dòng 2 tốn một đơn vị thời gian.
• Vòng lặp for tại dòng 3, biến i chạy từ 0 đến n – 2, nên vòng lặp này có n – 1 bước lặp.
• Tại mỗi bước lặp của vòng lặp for tại dòng 3, chương trình sẽ thực hiện:
  • Vòng lặp for tại dòng 4, biến j chạy từ 0 đến n-1-i-1, vậy vòng lặp này thực hiện n-i-1 bước lặp.
  • Tại mỗi bước lặp của vòng lặp tại dòng 4, chương trình thực hiện một lệnh so sánh tại dòng 5 và 3 lệnh để thực hiện việc đổi chỗ tại dòng 6 (nếu điều kiện thỏa mãn).

Tổng hợp lại, chương trình của thuật toán sắp xếp nổi bọt đưa ra có thời gian chạy là:

Bước 2. Xác định độ phức tạp O của thuật toán:

T(n) = 2n² – 2n + 1 = O(n²)

Bài 2 (SGK - tr.117). Viết lại thuật toán cần tính độ phức tạp thời gian:

          def Mystery(n):

                   r = 0

                   for i in range(n-1):

                             for j in range(i+1,n):

                                      for k in range(1,j):

                                                r = r+1

                   return r

Hàm đã cho trả về kết quả là:

• Ta thấy rằng r ban đầu bằng 0. Mỗi lần thực hiện câu lệnh ở dòng 6, r sẽ tăng lên 1 đơn vị. Do vậy, hàm đã cho trả về giá trị của r chính là số lần thực hiện phép tính tại dòng 6. Ta sẽ tính kết quả trả về của chương trình đã cho thông qua một hàm của n gọi là F(n). Để tính F(n), ta sẽ phân tích thời gian thực hiện của đoạn mã lệnh từ dòng 3 đến dòng 6.
• Vòng for ở dòng 3, biến i chạy từ 0 đến n – 2, vậy vòng lặp này thực hiện n – 1 bước lặp.
• Tại mỗi bước lặp tại dòng 3, chương trình thực hiện:
  • Vòng for ở dòng 3, biến i chạy từ 0 đến n – 2, vậy vòng lặp này thực hiện n – 1 bước lặp.
  • Tại mỗi bước lặp tại dòng 4, chương trình thực hiện:
    • Vòng lặp for tại dòng 5, biến k chạy từ 1 đến j - 1, nên vòng lặp này thực hiện j - 1 bước lặp.
    • Tại mỗi bước lặp tại dòng 5, chương trình thực hiện một lệnh gán tại dòng 6 tốn 1 đơn vị thời gian.

Vậy tổng thời gian thực hiện câu lệnh tại dòng từ 3 đến 6 là: