logo

Soạn Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp của thời gian thuật toán (trang 115, 117)

Hướng dẫn Soạn Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp của thời gian thuật toán trang 115, 117 ngắn gọn, hay nhất theo chương trình Sách mới.

Bài 25: Thực hành xác định độ phức tạp của thời gian thuật toán


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:

* Gợi ý:

Giả sử cần sắp xếp tăng dần một danh sách có n phần tử a0, a1, a2,…,an-1.

Bắt đầu từ đầu danh sách, duyệt từng phần tử và đưa phần tử đó về đúng vị trí trong dãy đã được sắp xếp tăng dần trước đó. Phần tử đầu tiên được coi là đã được sắp xếp.

Sau đó, sẽ không xét đến phần tử đầu tiên đó nữa ở bước tiếp theo. Do vậy, ở lần xử lý thứ i, phần tử đầu được xét sẽ có vị trí là i.

Lặp lại các bước xử lý trên cho đến khi không còn phần tử nào để xét.

Bước 1: i = 1;//lần xử lý đầu tiên

Bước 2: j = i;//duyệt từ vị trí i về đầu dãy

Trong khi (j > 0) và (a[j] < a[j-1]) xét trường hợp: Đổi chổ a[j] và a[j-1], sau đó j = j-1.

Bước 3: i = i+1; //lần xử lý kế tiếp

Nếu i = n -> hết dãy -> Dừng.

Ngược lại -> Lặp lại Bước 2.


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.

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:

Gợi ý: Nhập máy chương trình trên, đọc kết quả trả về

Xác định độ phức tạp thuật toán

  T(n) = O(f(n)+ g(n)) = O(max(f(n), g(n)))


3. 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:

* Gợi ý:

Để tìm 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 với thời gian thực thi là 1 giây, 1 phút và 1 giờ, ta cần tính số phép tính tối đa có thể thực hiện được trong khoảng thời gian đó và áp dụng công thức tính toán để suy ra giá trị của n.


4. 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.

* Gợi ý: 

- Tính chiều dài mảng

>>> Xem toàn bộ: Soạn Tin 11 Kết nối tri thức

-------------------------------------

Trên đây Toploigiai đã cùng các bạn Soạn Tin học 11 Kết nối tri thức Bài 25 trang 115, 117: Thực hành xác định độ phức tạp của thời gian thuật toán trong bộ SGK Kết nối tri thức theo chương trình sách mới. Chúng tôi hi vọng các bạn đã có kiến thức hữu ích khi đọc bài viết này. Click vào trang chủ Toploigiai để tham khảo và chuẩn bị bài cho năm học mới nhé. Chúc các bạn học tốt!

icon-date
Xuất bản : 24/02/2023 - Cập nhật : 19/07/2023

Tham khảo các bài học khác