[SGK Tin học Lớp 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 trang 115 SGK Tin học 11 Định hướng khoa học máy tính Kết nối tri thức
Hướng dẫn học bài: Bài 25. Thực hành xác định độ phức tạp thời gian thuật toán trang 115 SGK Tin học 11 Định hướng khoa học máy tính Kết nối tri thức - Môn Tin học Lớp 11 Lớp 11. Đây là sách giáo khoa nằm trong bộ sách 'SGK Tin học Lớp 11 Kết nối tri thức Lớp 11' được biên soạn theo chương trình đổi mới của Bộ giáo dục. Hi vọng, với cách hướng dẫn cụ thể và giải chi tiết các bé sẽ nắm bài học tốt hơn.
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?
Phương pháp giải:
Dựa vào kiến thức trong bài kết hợp kiến thức thực tế của bản thân để trả lời câu hỏi.
Lời giải chi tiết:
Đánh giá được mức đơn giản của thuật toán, từ đó tìm ra được cách giải nhanh nhất
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):
if A[j] > A[j+1]:
A[j],A[j+1] = A[j+1]1,A[j]
Phương pháp giải:
Dựa vào hướng dẫn của Nhiệm vụ 2 trang 116 SGK kết hợp kiến thức thực tế của bản thân để trả lời câu hỏi.
Lời giải chi tiết:
Độ phức tạp của thuật toán sắp xếp nổi bọt là O(n2)
T=O(n)+O(n2)=O(n2)
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.
def Mystery(n):
r=0
for i in range(n-1):
for j in range(i+1,n):
for k in range(1,j):
r=r+1
return r
Phương pháp giải:
Dựa vào hướng dẫn của Nhiệm vụ 1 trang 115 SGK kết hợp kiến thức thực tế của bản thân để trả lời câu hỏi.
Lời giải chi tiết:
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(n3)
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ờ?
Phương pháp giải:
Vận dụng kiến thức trong bài để trả lời câu hỏi.
Lời giải chi tiết:
1.Thuật toán tìm kiếm tuần tự:
- Độ phức tạp thời gian của thuật toán tìm kiếm tuần tự là O(n)
- Giá trị lớn nhất của n với thời gian thực thi là 1 giây: n = 1 giây * (106 us / phép tính) = 106
- Giá trị lớn nhất của n với thời gian thực thi là 1 phút: n = 1 phút * (60 giây / phút) * (106us / phép tính) = 6 * 107
- Giá trị lớn nhất của n với thời gian thực thi là 1 giờ: n = 1 giờ * (60 phút / giờ) * (60 giây / phút) * (106us / phép tính) = 3.6 * 109
2.Thuật toán sắp xếp chèn:
- Độ phức tạp thời gian của thuật toán sắp xếp chèn là O(102
- Giá trị lớn nhất của n với thời gian thực thi là 1 giây: n = sqrt(1 giây * (106us / phép tính)) =103
- Giá trị lớn nhất của n với thời gian thực thi là 1 phút: n = sqrt(1 phút * (60 giây / phút) * (106us / phép tính)) = 6 * 104
- Giá trị lớn nhất của n với thời gian thực thi là 1 giờ: n = sqrt(1 giờ * (60 phút / giờ) * (60 giây / phút) * (106us / phép tính)) = 3.6 * 106
3. Thuật toán sắp xếp chọn:
- Độ phức tạp thời gian của thuật toán sắp xếp chọn là O(n2)
- Giá trị lớn nhất của n là: n = sqrt(1 giây * (106us / phép tính)) = 1000.
Thời gian thực thi là 1 phút:
Giá trị lớn nhất của n là: n = sqrt(1 phút * (60 giây / phút) * (106us / phép tính)) = 60000.
Thời gian thực thi là 1 giờ:
Giá trị lớn nhất của n là: n = sqrt(1 giờ * (60 phút / giờ) * (60 giây / phút) * (106us / phép tính)) = 3.6 * 106
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.
def func(A):
n=len(A)
for i in range(n-1):
for j in range(i+1,n):
if A[j] > A[j]:
A[j],A[j] = A[j],A[i]
Phương pháp giải:
Vận dụng vào kiến thức trong bài kết hợp kiến thức thực tế của bản thân để trả lời câu hỏi.
Lời giải chi tiết:
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(n2)
Giải bài tập những môn khác
Môn Ngữ văn Lớp 11
Môn Toán học Lớp 11
Môn Vật lí Lớp 11
Môn Tiếng Anh Lớp 11
Môn Hóa học Lớp 11
Môn Sinh học Lớp 11
Môn GD kinh tế và pháp luật Lớp 11
Lời giải và bài tập Lớp 11 đang được quan tâm
