Đối với thuật toán LinearSearch(A, K), thời gian tính toán trong trường hợp tốt nhất là:
A. O(n)
Giải bởi Vietjack
Đáp án: C
Giải thích: Trong trường hợp tốt nhất, phần tử cần tìm có thể nằm ngay ở vị trí đầu tiên của mảng, và thuật toán chỉ cần thực hiện một lần so sánh để trả về kết quả, do đó độ phức tạp là O(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ức tạp thời gian của thuật toán tìm kiếm tuần tự LinearSearch(A, K) là:
Khi SelectionSort(A) thực hiện một phép đổi chỗ tại dòng cuối, phép tính này sẽ tốn:
Độ phức tạp thời gian của thuật toán sắp xếp chọn SelectionSort(A) là:
Độ phức tạp thời gian của hàm Mystery(n) với các vòng lặp lồng nhau từ i đến j và j đến k là:
Hàm func(A) với hai vòng lặp lồng nhau chạy từ 0 đến n-1, thực hiện một phép so sánh mỗi lần duyệt, có độ phức tạp là:
Trong các thuật toán tìm kiếm tuần tự, thời gian thực hiện tối đa sẽ là bao nhiêu đối với mảng kích thước n?
Độ phức tạp thời gian của thuật toán sắp xếp nổi bọt BubbleSort(A) là:
Nếu thời gian thực hiện thuật toán sắp xếp chọn là 1 giây, giá trị lớn nhất của n sẽ là:
Độ phức tạp thời gian của BubbleSort trong trường hợp tốt nhất khi mảng đã sắp xếp là:
