Tin học 11 Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán Giải Tin học 11 Định hướng Khoa học máy tính Kết nối tri thức

Giải bài tập SGK Tin học 11 trang 115→117 sách Kết nối tri thức với cuộc sống giúp các em học sinh lớp 11 xem gợi ý giải các câu hỏi Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán thuộc Chủ đề 6: Kỹ thuật lập trình.

Soạn Tin học 11 Kết nối tri thức Bài 25 giúp các bạn học sinh biết cách xác định độ phức tạp thời gian thuật toán. Đồng thời qua tài liệu này giúp giáo viên nhanh chóng xây dựng hoàn thiện giáo án dạy học của mình. Vậy sau đây là Giải Tin học 11 Định hướng Khoa học máy tính Bài 25 Kết nối tri thức mời các bạn cùng theo dõi.

Giải Luyện tập Tin học 11 Bài 25

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]

Gợi ý đáp án

Độ 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

Gợi ý đáp án

Đọc thêm:  Tại sao máy tính bảng không bắt được Wifi? Cách khắc phục đơn giản

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)

Giải Vận dụng Tin học 11 Bài 25

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

Gợi ý đáp án

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

Đọc thêm:  Review Ký túc xá Đại học Ngoại ngữ: Đơn xin vào, cơ sở vật chất, bao nhiêu tiền, nội quy, địa chỉ

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]

Gợi ý đáp án

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)

5/5 - (8623 bình chọn)
Cảm ơn các bạn đã đồng hành và theo dõi https://th-thule-badinh-hanoi.edu.vn/ !!!!. Hãy cho chúng tớ 1 like để tiếp tục phát triển nhều kiến thức mới nhất cho bạn đọc nhé !!!

Huyền Trân

Dương Huyền Trân có trình độ chuyên môn cao về giáo dục và hiện tại đang đảm nhận vị trí chuyên viên quản trị nội dung tại website: https://th-thule-badinh-hanoi.edu.vn/ . Để hoàn thành thật tốt công việc mà mình đang đảm nhận thì tôi phải nghiên cứu và phân tích quá trình hoạt động phát triển các dịch vụ, sản phẩm của từng ngành khác nhau.

Bài viết liên quan

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Back to top button