Giải bài 25: Xác định độ phức tạp thời gian thuộc toán | Tin học 11 Kết nối tri thức

Xin gửi tới bạn đọc bài viết Tin học 11 Kết nối tri thức bài 25: Xác định độ phức tạp thời gian thuộc toán để bạn đọc cùng tham khảo và có thêm tài liệu giải SGK Tin học 11 Kết nối tri thức nhé. Mời các bạn cùng theo dõi bài viết dưới đây.

68 34 lượt tải Tải xuống
Chia sẻ Báo cáo tài liệu

Chủ đề: Chủ đề 6: Kĩ thuật lập trình (KNTT)

Môn: Tin học 11

Sách: Kết nối tri thức

Thông tin:

2 trang 6 tháng trước

Tác giả:

Profile Thanh Hoa
Tin học 11 Kết nối tri thức bài 25
Khởi động
Câu hỏi. 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?
Bài làm
Đá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
Câu hỏi 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]
Bài làm
Độ phức tạp của thuật toán sắp xếp nổi bọt là O(n
2
)
T = O(n) + O(n
2
) = O(n
2
)
Câu hỏi 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.
Bài làm
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)))
Vận dụng
Câu hỏi 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ờ?
Bài làm
- 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
6
us / phép tính)) = 3.6 * 10
6
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
6
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
6
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
6
us /
phép tính)) = 3.6 * 10
6
Câu hỏi 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.
Bài làm
ef 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]
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(n
2
)
| 1/2
| | Tải xuống

Có thể bạn quan tâm:

Preview text:

Tin học 11 Kết nối tri thức bài 25 Khởi động
Câu hỏi. 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? Bài làm
Đá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
Câu hỏi 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] Bài làm
Độ 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)
Câu hỏi 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. Bài làm
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))) Vận dụng
Câu hỏi 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ờ? Bài làm
- 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
Câu hỏi 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. Bài làm ef 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]
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)
Document Outline

  • Khởi động
  • Luyện tập
  • Vận dụng