Tin học 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

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). Như vậy, 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. Như vậy, 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 1 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 Olớ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.

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:

Ý tưởng của thuật toán sắp xếp chọn là tại mỗi bước thứ i của vòng lặp sẽ tim chính xác phần tử tại vị trí thứ i, tức là sẽ tìm phần tử nhỏ nhất trong dãy từ A[i], A[i + 1], ..., An − 1] và đổi chỗ phần tử nhỏ nhất này với A[i].

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 lệnh 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à một lệnh gán tại dòng 7 tồn 1 đơn vị thời gian (nếu điều kiện thoả mãn).

Như vậy 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à:

\(\begin{align} & T(n)=1+\sum\limits_{i=0}^{n-2}{(1+2(n-i-1)+3)} \\ & T(n)=1+4(n-1)+2\sum\limits_{i=0}^{n-2}{(n-i-1)} \\ & T(n)=1+4(n-1)+2\sum\limits_{i=0}^{n-2}{k} \\ & T(n)=1+4(n-1)+n(n-1) \\ &T(n) = {n}^{2} + 3n -3 \end{align}\)

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.

Qua bài học này, các em sẽ: Thực hành xác định độ phức tạp (O-lớn) của hàm thời gian.

2.1. Trắc nghiệm Bài 25 SGK Tin học 11 Kết nối tri thức  

Như vậy là các em đã xem qua bài giảng Bài 25 Chủ đề 6 Tin học lớp 11 Kết nối tri thức. Để củng cố kiến thức bài học mời các em tham gia bài tập trắc nghiệm Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25.

Câu 4-10: Mời các em đăng nhập xem tiếp nội dung và thi thử Online để củng cố kiến thức về bài học này nhé!

Các em có thể xem thêm phần hướng dẫn Giải bài tập Tin học 11 Kết nối tri thức Bài 25 để giúp các em nắm vững bài học và các phương pháp giải bài tập.

Khởi động trang 115 SGK Tin học 11 Kết nối tri thức - KNTT

Luyện tập 1 trang 117 SGK Tin học 11 Kết nối tri thức - KNTT

Luyện tập 2 trang 117 SGK Tin học 11 Kết nối tri thức - KNTT

Vận dụng 1 trang 117 SGK Tin học 11 Kết nối tri thức - KNTT

Vận dụng 2 trang 117 SGK Tin học 11 Kết nối tri thức - KNTT

Trong quá trình học tập nếu có thắc mắc hay cần trợ giúp gì thì các em hãy comment ở mục Hỏi đáp, Cộng đồng Tin học của HOC247 sẽ hỗ trợ cho các em một cách nhanh chóng!

Chúc các em học tập tốt và luôn đạt thành tích cao trong học tập!