Xác định độ phức tạp của đoạn chương trình sau, với giá trị n

Xác định độ phức tạp của đoạn chương trình sau, với giá trị n > 0

Nguyễn Lê Khánh Vy Ngày: 23-01-2024 Lớp 11

139

Với giải Câu F^cs21 trang 52 SBT Tin học 11 Cánh diều chi tiết trong Bài 5: Đánh giá thuật toán giúp học sinh dễ dàng xem và so sánh lời giải, từ đó biết cách làm bài tập Tin học 11. Mời các bạn đón xem:

Xác định độ phức tạp của đoạn chương trình sau, với giá trị n > 0

Câu F^cs21 trang 52 SBT Tin học 11: Xác định độ phức tạp của đoạn chương trình sau, với giá trị n > 0 được cho ở dữ liệu đầu vào:

SBT Tin học 11 (Cánh diều) Bài 5: Đánh giá thuật toán (ảnh 3)

Lời giải:

Sau khi kết thúc lượt chạy i = 0, giá trị j sẽ tăng lên bằng n. Ở các lượt chạy sau đó của i thì vòng lặp while bên trong sẽ không được thực thi, nên độ phức tạp của cả chương trình chỉ là O(n).

Xem thêm các bài giải sách bài tập Tin học 11 Cánh diều hay, chi tiết khác:

Câu F^cs17 trang 51 SBT Tin học 11: Những phát biểu nào dưới đây là SAI?

Câu F^cs18 trang 51 SBT Tin học 11: Xét bài toán; Tính tổng bình phương các số tự nhiên từ 1 đến n, với n là một số tự nhiên lớn hơn 0. Nói cách khác, tính giá trị S = 1 + 2 + ... + (n - 1) + 1)2 n2.

Câu F^cs19 trang 52 SBT Tin học 11: Xét bài toán: Cho danh sách các số nguyên 4-4, a,,..., a ) khác nhau từng đôi một. Xác định phần tử có giá trị lớn thứ hai trong danh sách A. Em hãy xây dựng thuật toán để giải quyết bài toán trên với độ phức tạp:

Câu F^cs20 trang 52 SBT Tin học 11: Xác định độ phức tạp của đoạn chương trình sau, với giá trị N>0 được cho ở dữ liệu đầu vào:

Câu F^cs21 trang 52 SBT Tin học 11: Xác định độ phức tạp của đoạn chương trình sau, với giá trị n > 0 được cho ở dữ liệu đầu vào:

Xem thêm các bài giải sách bài tập Tin học 11 Cánh diều hay, chi tiết khác:

Bài 2, 3: Mảng hai chiều, Thực hành về tệp, mảng và danh sách

Bài 4: Làm mịn dần từng bước từ thuật toán đến chương trình máy tính

Bài 6: Kiểm thử và sửa lỗi chương trình

Bài 7: Lập trình giải bài toán tìm kiếm

Bài 8: Lập trình một số thuật toán sắp xếp