Câu hỏi:
30/11/2024 20Độ phức tạp thời gian của thuật toán sắp xếp chọn SelectionSort là gì và tại sao?
Sách mới 2k7: Tổng ôn 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ừ 110k).
Quảng cáo
Trả lời:
Giải bởi Vietjack
Đáp án: O(n²)
Giải thích: Thuật toán sắp xếp chọn SelectionSort hoạt động bằng cách tìm phần tử nhỏ nhất trong phần mảng chưa được sắp xếp và hoán đổi nó vào vị trí đúng trong mảng đã sắp xếp. Trong mỗi lần lặp, thuật toán cần duyệt qua phần còn lại của mảng để tìm phần tử nhỏ nhất, dẫn đến số phép tính tăng lên theo bình phương của n. Vì vậy, độ phức tạp thời gian của thuật toán là O(n²), đặc biệt khi kích thước mảng lớn.
Nhà sách VIETJACK:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Độ phức tạp thời gian của thuật toán sắp xếp chọn SelectionSort(A) là gì?
a) O(1)O(1)O(1)
b) O(n)O(n)O(n)
c) O(nlogn)
d) O(n2)O(n^2)O(n2)
Xem đáp án »
30/11/2024
48
Câu 2:
Độ phức tạp thời gian của thuật toán sắp xếp nổi bọt BubbleSort(A) là:
Xem đáp án »
30/11/2024
34
Câu 3:
Độ phức tạp thời gian của thuật toán sắp xếp chọn SelectionSort(A) là:
Xem đáp án »
30/11/2024
28
Câu 4:
PHẦN III. Câu trả lời ngắn. Thí sinh trả lời từ câu 1 đến câu 3
PHẦN III. Câu trả lời ngắn. Thí sinh trả lời từ câu 1 đến câu 3
Độ phức tạp thời gian của thuật toán tìm kiếm tuần tự LinearSearch là gì và tại sao?
Xem đáp án »
30/11/2024
22
Câu 5:
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
Độ phức tạp thời gian của thuật toán tìm kiếm tuần tự LinearSearch(A, K) là gì?
a) O(1)
b) O(logn)
c) O(n)O(n)O(n)
d) O(n2)O(n^2)O(n2)
Xem đáp án »
30/11/2024
16
Câu 6:
Giả sử mỗi phép tính tốn một micro giây, giá trị lớn nhất của n mà thuật toán tìm kiếm tuần tự có thể thực hiện trong một giây là bao nhiêu?
Xem đáp án »
30/11/2024
15
về câu hỏi!