Select the most correct statement about the complexity of selection sort
4 phương ánCó giải thích
Các phương án trả lời
Chọn một phương ánLời giảiChọn phương án để mở
Đáp án đúng: "Both best and worst cases are O(n^2)". Sắp xếp chọn luôn phải quét hết phần chưa sắp để biết phần tử nhỏ nhất nằm đâu, nên lượt thứ i tốn n−i phép so sánh và tổng luôn là n(n−1)/2, không phụ thuộc dữ liệu đầu vào. Mảng đã sắp sẵn cũng không giúp gì vì thuật toán không có cờ nào để dừng sớm; cái duy nhất giảm được là số phép đổi chỗ. Phương án "The best case is O(n), and the worst case is O(n^2)" là đặc trưng của sắp xếp nổi bọt có kiểm tra lượt không hoán vị, hoặc của sắp xếp chèn. Phương án "The best case is O(n), and the average case is O(nlogn)" trộn hai thuật toán khác: mức n log n thuộc sắp xếp trộn hoặc sắp xếp nhanh. Phương án "The best case is O(n), and the average case is O(n^2)" đúng phần trung bình nhưng vẫn cho trường hợp tốt là O(n), trong khi trường hợp tốt vẫn tốn n(n−1)/2 phép so sánh.
Cùng phần 6
Select the most correct statement about the complexity of bubble sortCó lời giảiCâu hỏiThe following is the main part of insertion sort pseudocode:
for i := 1 to n-1
insert a[i] into sorted sublist {a[0],...,a[i-1]}
so that the sortedness is still kept.
end for
Select the most correct solution:
Consider the list of ten integers below:
16, 5, 2, 11, 10, 8, 12, 3, 8, 6
What is the list after the FIRST TWO steps of insertion sort? (sorting from smallest to largest).Có lời giảiCâu hỏiThe following is the main part of bubble sort pseudocode:
do
swapped := false
for i := 0 to n-2
if a[i] > a[i+1] then
swap(a[i],a[i+1])
swapped := true
end if
end for
while swapped
Consider the list of ten integers below:
5, 3, 9, 10, 1, 8, 0, 2, 6, 4
What is the list after the FIRST iteration (for i = 0 to n-2) in a bubble sort? (sorting from smallest to largest).Có lời giảiCâu hỏiCả 20 câu của chủ đề20 câu
Xuất hiện trong 1 bộ đề
Đi tiếp từ đây