1 of 30

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

2 of 30

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.

3 of 30

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

4 of 30

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

5 of 30

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

6 of 30

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

7 of 30

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

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

Hướng dẫn:

8 of 30

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.

9 of 30

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]

10 of 30

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.

11 of 30

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

12 of 30

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

13 of 30

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.

14 of 30

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]

15 of 30

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.

16 of 30

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

17 of 30

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)

18 of 30

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

19 of 30

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.

20 of 30

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

21 of 30

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

22 of 30

23 of 30

Từ đó suy ra thời gian thực hiện chương trình là:

 

 

24 of 30

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

25 of 30

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ả

26 of 30

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.

27 of 30

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:

  • Lệnh gán tại dòng 2 tốn 1 đơn vị thời gian.
  • Vòng for tại dòng 3, biến i chạy từ 0 đến n-2, vậy vòng lặp thực hiện n-1 bước lặp.
  • Với mỗi bước lặp tại dòng 3, chương trình thực hiện:
  • Vòng lặp tại dòng 4, biến j chạy từ i+1 đến n-1, vậy vòng lặp thực hiện (n-i-1) bước lặp.
  • Tại mỗi bước lặp tạo dòng 4, chương trình thực hiện việc đổi chỗ gồm 3 lệnh tương ứng với 3 đơn vị thời gian.

28 of 30

Tổng hợp lại, thuật toán có thời gian chạy là:

 

29 of 30

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

30 of 30