Giải Tin học 11 trang 117 Kết nối tri thức

---

Haylamdo biên soạn và sưu tầm với Giải Tin học 11 trang 117 trong Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán Tin học lớp 11 Kết nối tri thức hay nhất, ngắn gọn sẽ giúp học sinh dễ dàng trả lời các câu hỏi & làm bài tập Tin 11 trang 117.

Giải Tin học 11 trang 117 Kết nối tri thức

Luyện tập 1 trang 117 Tin học 11: 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]

Lời giải:

Độ phức tạp của thuật toán sắp xếp nổi bọt là O(n²)

T=O(n)+O(n²)=O(n²)

Luyện tập 2 trang 117 Tin học 11: 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

Lời giải:

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(n³)

Vận dụng 1 trang 117 Tin học 11: 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ờ?

Lời giải:

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 * (10⁶ us / phép tính) = 10⁶

- 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) * (10⁶us / phép tính) = 6 * 10⁷

- 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) * (10⁶us / phép tính) = 3.6 * 10⁹

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(10²

- 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 * (10⁶us / phép tính)) =10³

- 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) * (10⁶us / phép tính)) = 6 * 10⁴

- 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) * (10⁶us / phép tính)) = 3.6 * 10⁶

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 * (10⁶us / 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) * (10⁶us / 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) * (10⁶us / phép tính)) = 3.6 * 10⁶

Vận dụng 2 trang 117 Tin học 11: 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]

Lời giải:

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)