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

PHẦN I. HỆ THỐNG CÂU HỎI, BÀI TẬP TRONG SGK

KHỞI ĐỘNG

Biết cách phân tích, đánh giá độ phức tạp thuật toán là kĩ năng quan trọng của người thiết kế thuật toán và chương trình. 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?

LUYỆN TẬP

Luyện tập 1: 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):

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

A[j],A{fj+1] = A[3+1]1,A[3]

Luyện tập 2: Cho biết hàm sau sẽ trả về giá trị là bao nhiêu? Xác định độ phức tạp thời gian O- lớn của chương trình.

VẬN DỤNG

Vận dụng 1: Giả sử rằng mỗi phép tính đơn được thực hiện trong micro giây (1 us = một phần triệu giây). Hãy xác định giá trị lớn nhất của n trong các thuật toán tìm kiếm tuần tự, sắp xếp chèn và sắp xếp chọn nếu thời gian thực thi các thuật toán là 1 giây, 1 phút và 1 giờ?

Vận dụng 2: Hãy cho biết hàm sau thực hiện công việc gì? Xác định độ phức tạp thời gian của thuật toán.

PHẦN II. 5 PHÚT TRẢ LỜI CÂU HỎI, BÀI TẬP SGK

KHỞI ĐỘNG

Đáp án KD:

Đánh giá được mức đơn giản của thuật toán.

LUYỆN TẬP

Đáp án LT1: 

O(n²). T=O(n)+O(n²)=O(n²)

Đáp án LT2: 

Hàm "Mystery(n)" sẽ trả về giá trị là r. Độ phức tạp thời gian của chương trình này là O(n³)

VẬN DỤNG

Đáp án VD1:

1. Thuật toán tìm kiếm tuần tự:

• Độ phức tạp là O(n)
• n_max với thời gian thực thi là 1 giây: n = 1 giây * (10⁶ us / phép tính) = 10⁶
• n_max với thời gian thực thi là 1 phút: n = 1 phút * (60 giây / phút) * (10⁶us / phép tính) = 6 * 10⁷
• n_max với thời gian thực thi là 1 giờ: n = 1 giờ * (60 phút / giờ) * (60 giây / phút) * (10⁶us / phép tính) = 3.6 * 10⁹

2. Thuật toán sắp xếp chèn:

• Độ phức tạp là O(10²
• n_max với thời gian thực thi là 1 giây: n = sqrt(1 giây * (10⁶us / phép tính)) =10³
• n_max với thời gian thực thi là 1 phút: n = sqrt(1 phút * (60 giây / phút) * (10⁶us / phép tính)) = 6 * 10⁴
• n_max với thời gian thực thi là 1 giờ: n = sqrt(1 giờ * (60 phút / giờ) * (60 giây / phút) * (10⁶us / phép tính)) = 3.6 * 10⁶

3. Thuật toán sắp xếp chọn:

• Độ phức tạp là O(n2)
• Giá trị lớn nhất của n = sqrt(1 giây * (10⁶us / phép tính)) = 1000.
• Thời gian thực thi là 1 phút: Giá trị lớn nhất của n = sqrt(1 phút * (60 giây / phút) * (10⁶us / phép tính)) = 60000.
• Thời gian thực thi là 1 giờ: Giá trị lớn nhất của n = sqrt(1 giờ * (60 phút / giờ) * (60 giây / phút) * (10⁶us / phép tính)) = 3.6 * 10⁶

Đáp án VD2:

Công việc của hàm là thực hiện sắp xếp. Độ phức tạp của thuật toán là O(n²)