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
01
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ự
02
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
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:
1 def LinearSearch(A,K):
2 for i in range(len(A)):
3 if A[i] == K:
4 return i
5 return -1
Hướng dẫn:
Bước 1. Phân tích thời gian tính toán của thuật toán.
Bước 1. Phân tích thời gian tính toán của thuật toán.
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.
Hướng dẫn:
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:
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]
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:
→ Mỗi bước lặp tại dòng 5 sẽ tốn tối đa 2 đơ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(n2, 3n, –3)) = O(n2)
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:
1 def BubbleSort(A):
2 n = len(A)
3 for i in range(n-1):
4 for j in range(n-1-i):
5 if A[j] > A[j+1]:
6 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:
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) = 2n2 – 2n + 1 = O(n2)
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:
1 def Mystery(n):
2 r = 0
3 for i in range(n-1):
4 for j in range(i+1,n):
5 for k in range(1,j):
6 r = r+1
7 return r
Hàm đã cho trả về kết quả là:
Vậy tổng thời gian thực hiện câu lệnh tại dòng từ 3 đến 6 là:
Đặt k = n – 2 ta có:
Từ đó suy ra thời gian thực hiện chương trình là:
VẬN DỤNG
Bài 1 (SGK - tr.117). Giả sử mỗi phép tính đơn được thực hiện trong 1 micro giây (1μs = 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ờ.
Thuật toán tìm kiếm tuần tự có độ phức tạp là O(n). Thuật toán sắp xếp chèn và sắp xếp chọn có độ phức tạp là O(n2).
Giả sử mỗi phép tính được thực hiện trong 1 micro giây, khi đó giá trị lớn nhất của n trong các thuật toán trên nếu thời gian thực hiện tương ứng 1 giây, 1 phút, 1 giờ được thể hiện như bảng sau:
Thuật toán | Giá trị lớn nhất của n | ||
1 giây | 1 phút | 1 giờ | |
Tìm kiếm tuần tự (O(n)) | 1 000 000 | 60 000 000 | 360 000 000 |
Sắp xếp chèn, chọn (O(n2)) | 1000 | 7 746 | 18 974 |
Kết quả
Bài 2 (SGK-tr.117). 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.
1 def func(A):
2 n = len(A)
3 for i in range(n-1):
4 for j in range(i+1,n):
5 if A[i] > A[j]:
6 A[i],A[j] = A[j],A[i]
Hàm đã cho thực hiện việc sắp xếp mảng A theo thứ tự tăng dần.
Xác định độ phức tạp thời gian 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ính như sau:
Tổng hợp lại, thuật toán có thời gian chạy là:
HƯỚNG DẪN VỀ NHÀ
1
Ôn tập kiến thức đã học
2
Hoàn thành bài tập trong SBT
3
Chuẩn bị bài sau - Bài 26