MỞ ĐẦU

Câu 1: 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?

Trả lời:

Đánh giá mức đơn giản của thuật toán, từ đó tìm ra cách giải nhanh nhất.

LUYỆN TẬP

Câu 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]

Trả lời:

Độ phức tạp: O(n2)

T=O(n)+O(n2)=O(n2)

Câu 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.

Trả lời:

r

Độ phức tạp: O(n3)

VẬN DỤNG

Câu 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ờ?

Trả lời:

1. Tìm kiếm tuần tự:

Độ phức tạp: O(n)

• 1 giây: n = 1 giây * (106 us / phép tính) = 106
• 1 phút: n = 1 phút * (60 giây / phút) * (106us / phép tính) = 6 * 107
• 1 giờ: n = 1 giờ * (60 phút / giờ) * (60 giây / phút) * (106us / phép tính) = 3.6 * 109

2. Sắp xếp chèn:

Độ phức tạp: O(102 )

• 1 giây: n = sqrt(1 giây * (106us / phép tính)) =103

• 1 phút: n = sqrt(1 phút * (60 giây / phút) * (106us / phép tính)) = 6 * 104

• 1 giờ: n = sqrt(1 giờ * (60 phút / giờ) * (60 giây / phút) * (106us / phép tính)) = 3.6 * 106

3. Sắp xếp chọn:

Độ phức tạp: O(n2)

• Giá trị lớn nhất của n là: n = sqrt(1 giây * (106us / phép tính)) = 1000.

1 phút:

n = sqrt(1 phút * (60 giây / phút) * (106us / phép tính)) = 60000.

1 giờ:

n = sqrt(1 giờ * (60 phút / giờ) * (60 giây / phút) * (106us / phép tính)) = 3.6 * 106

Câu 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.

Trả lời:

Thực hiện sắp xếp.

Độ phức tạp: O(n2)