Câu hỏi:
17/11/2024 72Cách nào dưới đây có độ phức tạp thời gian tuyến tính?
a) Tìm số lớn nhất trong dãy số bằng cách so sánh từng cặp.
b) Tính giai thừa của một số nguyên n bằng đệ quy.
c) Sắp xếp một dãy số bằng thuật toán Quick Sort.
d) Tìm kiếm một số trong dãy số không sắp xếp bằng cách lặp qua từng phần tử.
Sách mới 2k7: Sổ tay Toán, Lí, Hóa, Văn, Sử, Địa... kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 30k).
Quảng cáo
Trả lời:
Giải bởi Vietjack
a) Đúng – Độ phức tạp thời gian là O(n) vì phải duyệt qua từng phần tử để so sánh.
b) Sai – Độ phức tạp thời gian là O(n) nhưng không được coi là tuyến tính trong trường hợp này do bản chất của đệ quy liên quan đến nhiều lời gọi hàm chồng chéo.
c) Sai. Thuật toán Quick Sort có độ phức tạp thời gian trung bình là O(nlogn)
d) Đúng. Tìm kiếm một số trong dãy số không sắp xếp bằng cách lặp qua từng phần tử có độ phức tạp thời gian O(n), vì phải kiểm tra tất cả n phần tử.
Nhà sách VIETJACK:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
PHẦN I. Câu trắc nghiệm nhiều phương án lựa chọn. Thí sinh trả lời từ câu 1 đến câu 10. Mỗi câu hỏi thí sinh chỉ lựa chọn một phương án.
PHẦN I. Câu trắc nghiệm nhiều phương án lựa chọn. Thí sinh trả lời từ câu 1 đến câu 10. Mỗi câu hỏi thí sinh chỉ lựa chọn một phương án.
Độ phức tạp thời gian của thuật toán được xác định bởi yếu tố nào?
Xem đáp án »
17/11/2024
304
Câu 7:
PHẦN II. Câu trắc nghiệm đúng sai. Thí sinh trả lời từ câu 1 đến câu 2. Trong mỗi ý a), b), c), d) ở mỗi câu, thí sinh chọn đúng hoặc sai
PHẦN II. Câu trắc nghiệm đúng sai. Thí sinh trả lời từ câu 1 đến câu 2. Trong mỗi ý a), b), c), d) ở mỗi câu, thí sinh chọn đúng hoặc sai
Thuật toán nào sau đây có độ phức tạp thời gian hằng số?
a) Tính tổng dãy số bằng cách cộng dồn từng số.
b) Tính tổng dãy số bằng công thức tính tổng cấp số cộng S=
c) Tìm kiếm một phần tử trong danh sách đã sắp xếp bằng cách sử dụng thuật toán tìm kiếm nhị phân.
d) Sắp xếp một dãy số bằng thuật toán sắp xếp nổi bọt (bubble sort).
Xem đáp án »
17/11/2024
123
Bình luận
🔥 Đề thi HOT:
-
15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Quản trị cơ sở dữ liệu trên máy tính có đáp án
-
15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 14 có đáp án
-
15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 11 có đáp án
-
15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 16 có đáp án
-
15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Thực hành xác định cấu trúc bảng và các trường khóa có đáp án
-
15 câu Trắc nghiệm Tin học 11 Cánh diều Làm quen với Microsoft Access có đáp án
-
15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 15 có đáp án
-
15 câu Trắc nghiệm Tin học 11 Cánh diều Bảng và khóa chính trong cơ sở dữ liệu quan hệ có đáp án
về câu hỏi!