2. Lớp 11
  3. Tin học

Câu hỏi:

13/07/2024 233

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?

Xem lời giải

Câu hỏi trong đề: Giải SGK Tin học 11 KNTT Bài 25. Thực hành xác định độ phức tạp thời gian thuật toán có đáp án !!

Bắt đầu thi Lưu câu hỏi

Quảng cáo

Trả lời:

verified
Giải bởi Vietjack

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

Hot: Học hè online Toán, Văn, Anh...lớp 1-12 tại Vietjack với hơn 1 triệu bài tập có đáp án. Học ngay

Sách thầy cô Vietjack biên soạn:
Xem thêm »
  1. Trọng tâm Sử, Địa, GD KTPL 11 cho cả 3 bộ Kết nối, Chân trời, Cánh diều VietJack - Sách 2025 ( 38.000₫ )
  2. Sách - Sổ tay kiến thức trọng tâm Vật lí 11 VietJack - Sách 2025 theo chương trình mới cho 2k8 ( 45.000₫ )
  3. Sách lớp 11 - Trọng tâm Toán, Lý, Hóa, Sử, Địa lớp 11 3 bộ sách KNTT, CTST, CD VietJack ( 52.000₫ )
  4. Sách lớp 10 - Combo Trọng tâm Toán, Văn, Anh và Lí, Hóa, Sinh cho cả 3 bộ KNTT, CD, CTST VietJack ( 75.000₫ )

Bình luận


Bình luận

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 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]

Lời giải

Độ 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)Top of Form

Câu 2

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 * (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

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 * 106Bottom of Form

 

Câu 3

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

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Câu 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.

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

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Xem thêm các câu hỏi khác »
Hỏi bài tập
Vietjack official store
Đăng ký gói thi VIP

VIP +1 - Luyện thi tất cả các đề có trên Website trong 1 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

VIP +3 - Luyện thi tất cả các đề có trên Website trong 3 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

VIP +6 - Luyện thi tất cả các đề có trên Website trong 6 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

VIP +12 - Luyện thi tất cả các đề có trên Website trong 12 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

🔥 Đề thi HOT:

  1. 358 người thi tuần này

    Bộ 4 đề thi cuối học kì 2 Tin 11 Kết nối tri thức có đáp án (Đề 2)
  2. 307 người thi tuần này

    Bộ 4 đề thi cuối học kì 2 Tin 11 Kết nối tri thức có đáp án (Đề 1)
  3. 286 người thi tuần này

    15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 26 có đáp án
  4. 283 người thi tuần này

    15 câu Trắc nghiệm Tin học 11 Cánh diều Bài 1: Một số thao tác chỉnh sửa ảnh và hỗ trợ chỉnh sửa ảnh có đáp án
  5. 223 người thi tuần này

    15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25 có đáp án
  6. 210 người thi tuần này

    15 câu Trắc nghiệm Tin học 11 Cánh diều Bài 2: Tẩy xóa ảnh có đáp án
  7. 208 người thi tuần này

    15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 27 có đáp án
  8. 197 người thi tuần này

    Bộ 4 đề thi giữa học kì 2 Tin 11 Kết nối tri thức có đáp án (Đề 4)

CÔNG TY TNHH ĐẦU TƯ VÀ DỊCH VỤ GIÁO DỤC VIETJACK
Giấy chứng nhận ĐKKD số: 0108307822 do Sở KH & ĐT TP Hà Nội cấp lần đầu ngày 04/06/2018
© 2017 Vietjack37. All Rights Reserved.

Đăng ký

Bạn đã có tài khoản?