Thcslytutrongst.edu.vn - Thông Tin Kiến Thức Bổ Ích

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

Tháng mười một 16, 2023 by Thcslytutrongst.edu.vn

Bạn đang xem bài viết 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 tại Thcslytutrongst.edu.vn bạn có thể truy cập nhanh thông tin cần thiết tại phần mục lục bài viết phía dưới.

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.

Mục Lục Bài Viết

  • Giải Luyện tập Tin học 11 Bài 25
    • Luyện tập 1
    • Luyện tập 2
  • Giải Vận dụng Tin học 11 Bài 25
    • Vận dụng 1
    • Vận dụng 2

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]

Khám Phá Thêm:   Đề cương ôn tập học kì 2 môn Toán lớp 2 năm 2023 - 2024 (Sách mới) Ôn thi học kì 2 lớp 2 môn Toán sách KNTT, CTST, Cánh diều

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

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

Khám Phá Thêm:   Viết: Luyện tập quan sát, tìm ý cho bài văn miêu tả con vật - Tiếng Việt 4 Chân trời sáng tạo Tiếng Việt lớp 4 Chân trời sáng tạo tập 2 Bài 8

– 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]

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)

Cảm ơn bạn đã xem bài viết 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 tại Thcslytutrongst.edu.vn bạn có thể bình luận, xem thêm các bài viết liên quan ở phía dưới và mong rằng sẽ giúp ích cho bạn những thông tin thú vị.

Khám Phá Thêm:   Văn mẫu lớp 9: Đoạn văn nghị luận về bạo lực học đường Dàn ý & 21 đoạn văn nghị luận về hiện tượng đời sống lớp 9

 

Bài Viết Liên Quan

Hướng dẫn tắt kiểm tra chính tả trên Windows 10
Cách trình bày bài dự thi Đại sứ văn hóa đọc 2025
Phim Hit the Spot: Nội dung, diễn viên và lịch chiếu phim
Previous Post: « So sánh biện pháp phòng trị một số bệnh phổ biến ở trâu, bò Một số bệnh phổ biến ở trâu, bò và biện pháp phòng, trị
Next Post: Tiếng Anh 11: Review Unit 3 Soạn Anh 11 Chân trời sáng tạo trang 47 »

Primary Sidebar

Công Cụ Hôm Nay

  • Thời Tiết Hôm Nay
  • Tử Vi Hôm Nay
  • Lịch Âm Hôm Nay
  • Lịch Thi Đấu Bóng Đá Hôm Nay
  • Giá Vàng Hôm Nay
  • Tỷ Giá Ngoaị Tệ Hôm Nay
  • Giá Xăng Hôm Nay
  • Giá Cà Phê Hôm Nay

Công Cụ Online

  • Photoshop Online
  • Casio Online
  • Tính Phần Trăm (%) Online
  • Giải Phương Trình Online
  • Ghép Ảnh Online
  • Vẽ Tranh Online
  • Làm Nét Ảnh Online
  • Chỉnh Sửa Ảnh Online
  • Upload Ảnh Online
  • Paint Online
  • Tạo Meme Online
  • Chèn Logo Vào Ảnh Online

Liên Kết Giới Thiệu

Copyright © 2025 · Thcslytutrongst.edu.vn - Thông Tin Kiến Thức Bổ Ích