Soạn mới giáo án Khoa học máy tính 11 kết nối tri thức bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

HOẠT ĐỘNG CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Bước 1: GV chuyển giao nhiệm vụ:

- GV chia lớp thành các nhóm từ 2 – 4 HS.

- GV chiếu nhiệm vụ học tập:

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:

1  def LinearSearch(A,K):

2      for i in range(len(A)):

3          if A[i] == K:

4             return i

5      return -1

- GV hướng dẫn HS theo hai bước:

Bước 1. Phân tích thời gian tính toán của thuật toán dựa vào phân tích các câu lệnh để tính tổng số phép tính cơ bản của chương trình.

Bước 2. Từ tổng số phép tính cơ bản của chương trình, GV hướng dẫn HS xác định độ phức tạp của thuật toán.

Bước 2: HS thực hiện nhiệm vụ học tập:

- HS lắng nghe GV hướng dẫn, thực hiện nhiệm vụ.

- GV quan sát và trợ giúp HS.

Bước 3: Báo cáo kết quả hoạt động, thảo luận:

- HS báo cáo kết quả 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ự.

- HS khác nhận xét, bổ sung cho bạn.

Bước 4: Đánh giá kết quả thực hiện:

- Sau khi HS hoàn thành chương trình, GV nhận xét và tổng kết nội dung nhiệm vụ 1.

- GV chuyển sang hoạt động tiếp theo.

Nhiệm vụ 1

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).

→ Chương trình có thể kết thúc khi chưa duyệt hết mảng (trường hợp đã tìm thấy phần tử) và tối đa là duyệt hết mảng.

→ Trong trường hợp tồi nhất vòng lặp ở dòng 2 sẽ thực hiện n bước lặp, mỗi bước lặp sẽ thực hiện lệnh so sánh ở dòng 3 tốn 1 đơn vị thời gian.

- 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.

HOẠT ĐỘNG CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Bước 1: GV chuyển giao nhiệm vụ:

- GV chiếu nhiệm vụ học tập:

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:

1 def SelectionSort(A):

2    n = len(A)

3    for i in range(n-1):

4        iMin = 1

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

6            if A[j] < A[iMin]:

7                iMin = j

8        A[i],A[iMin] = A[iMin],A[i]

- GV hướng dẫn HS theo hai bước:

Bước 1. Phân tích thời gian tính toán của thuật toán dựa vào phân tích các câu lệnh để tính tổng số phép tính cơ bản của chương trình.

Bước 2. Từ tổng số phép tính cơ bản của chương trình, GV hướng dẫn HS xác định độ phức tạp của thuật toán.

Bước 2: HS thực hiện nhiệm vụ học tập:

- HS lắng nghe GV hướng dẫn, thực hiện nhiệm vụ.

- GV quan sát và trợ giúp HS.

Bước 3: Báo cáo kết quả hoạt động, thảo luận:

- HS báo cáo kết quả xác định độ phức tạp thời gian tính toán của thuật toán sắp xếp chọn.

- HS khác nhận xét, bổ sung cho bạn.

Bước 4: Đánh giá kết quả thực hiện:

- Sau khi HS hoàn thành chương trình, GV nhận xét và tổng kết nội dung nhiệm vụ 2.

- GV chuyển sang hoạt động luyện tập.

Nhiệm vụ 2

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à:

T(n) = 1 +

T(n) =

T(n) =

T(n) =

T(n) = n² + 3n – 3.

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.