Câu hỏi:

17/11/2024 401 Lưu

Độ phức tạp thời gian tuyến tính có ý nghĩa gì trong việc đánh giá thuật toán?

Quảng cáo

Trả lời:

verified Giải bởi Vietjack

Đáp án: Độ phức tạp thời gian tuyến tính có nghĩa là số phép toán thực hiện tỷ lệ thuận với kích thước đầu vào.

Giải thích: Khi một thuật toán có độ phức tạp thời gian tuyến tính, điều này cho thấy rằng thời gian thực hiện sẽ tăng lên theo từng đơn vị kích thước dữ liệu. Ví dụ, nếu một thuật toán phải kiểm tra từng phần tử trong danh sách để tìm một giá trị cụ thể, thì số phép toán sẽ tương ứng với số lượng phần tử trong danh sách. Nếu danh sách có n phần tử, thì số phép toán sẽ là n, ký hiệu là T(n) = n, tức là O(n).

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

Lời giải

Đáp án: A

Giải thích: Độ phức tạp thời gian chủ yếu phụ thuộc vào kích thước dữ liệu đầu vào (n). Các yếu tố khác như ngôn ngữ lập trình hay kỹ năng lập trình viên có thể ảnh hưởng đến hiệu suất thực tế nhưng không phải là yếu tố chính để xác định độ phức tạp.

Câu 2

A. Khi thực hiện một lần lặp qua n phần tử

B. Khi thực hiện hai lần lặp lồng nhau qua n phần tử
C. Khi thực hiện tìm kiếm nhị phân
D. Khi thực hiện phép cộng n số

Lời giải

Đáp án: B

Giải thích: Độ phức tạp thời gian O(n^2) xảy ra khi có hai vòng lặp lồng nhau, mỗi vòng lặp chạy qua n phần tử.

Câu 3

A. Tìm kiếm một phần tử trong danh sách

B. Tính tổng dãy số từ 1 đến n bằng công thức
C. Sắp xếp một danh sách số
D. Tính giai thừa của 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

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 5

A. Tính toán độ phức tạp thực tế của một thuật toán

B. Tìm số phép toán tối thiểu và tối đa cần thiết cho một thuật toán
C. Xác định ước lượng trung bình cho tất cả các trường hợp
D. Lựa chọn phương pháp ước lượng đảm bảo không vượt quá giá trị ước tính

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 6

A. Phép nhân hai số

B. Phép lặp qua một dãy số
C. Phép so sánh hai giá trị
D. Phép khai thác giá trị tuyệt đối

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