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

Sách bài tập Tin học 11 Bài 5: Đánh giá thuật toán - Cánh diều

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:

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

Lời giải SBT Tin 11 Bài 5: Đánh giá thuật toán hay 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 ....

• 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ị ....

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