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^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:

Lời giải:

Vì giá trị của i bị giảm đi một nửa sau mỗi bước và vòng lặp sẽ dừng khi i = 0, nên độ phức tạp của chương trình là O(log,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^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 ....