Câu hỏi:

13/07/2024 829

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]

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

Quảng cáo

Trả lời:

Giải bởi Vietjack

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

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 »

Bình luận

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

Câu 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ờ?

Xem đáp án

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⁶Bottom of Form

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

Xem đáp án

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

Câu 3

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]

Xem đáp án

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

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 đáp án

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

Đăng ký gói thi VIP

VIP +1 tháng ( 199,000 VNĐ )

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 tháng ( 299,000 VNĐ )

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 tháng ( 399,000 VNĐ )

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 tháng ( 499,000 VNĐ )

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

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]

Bình luận

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

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]

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?

VIP +1 tháng ( 199,000 VNĐ )

VIP +3 tháng ( 299,000 VNĐ )

VIP +6 tháng ( 399,000 VNĐ )

VIP +12 tháng ( 499,000 VNĐ )

🔥 Đề thi HOT:

CHỌN BỘ SÁCH BẠN MUỐN XEM

Đăng ký

Đăng nhập

Quên mật khẩu

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]

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

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]