Select the most correct statement about the complexity of heapsort
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(nlogn)". Sắp xếp vun đống luôn gồm hai phần cố định: dựng đống từ n phần tử rồi lặp n lần việc lấy phần tử lớn nhất ở gốc, đưa về cuối và vun lại. Mỗi lần vun lại đi dọc một đường từ gốc xuống lá nên tốn cỡ log n, lặp n lần cho n log n, và không có dạng dữ liệu nào cắt bớt được các lần vun ấy, kể cả mảng đã sắp xếp sẵn. Mức "The best case is O(n), and the worst case is O(nlogn)" cho trường hợp tốt nhất là tuyến tính, nhưng dù mảng đã có thứ tự thì thuật toán vẫn phải vun lại sau từng lần lấy gốc nên không xuống được mức n. Mức "The best case is O(n), and the worst case is O(n^2)" vừa nêu trường hợp tốt nhất tuyến tính vừa cho trường hợp xấu nhất bình phương, đó là dáng của sắp xếp chèn có kiểm tra mảng đã xong. Mức "Best case is O(nlogn) , the worst case is O(n^2)" cho trường hợp xấu nhất bình phương, đó là dáng của sắp xếp nhanh khi chốt chọn lệch, còn vun đống không phụ thuộc việc chọn chốt.
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