Select the most correct statement about the complexity of mergesort
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)". Mergesort chia mảng làm hai nửa theo chỉ số giữa, hoàn toàn không phụ thuộc giá trị dữ liệu, nên cây đệ quy luôn sâu khoảng log2(n) mức; ở mỗi mức phép trộn quét qua đủ n phần tử, cho tổng khoảng n nhân log2(n) cho cả trường hợp tốt nhất lẫn xấu nhất. Phương án "The best case is O(n), and the worst case is O(nlogn)" sai vì ngay cả khi mảng đã sắp sẵn, bản mergesort chuẩn vẫn trộn từng cặp nửa ở mọi mức, không có bước dò nào cho phép bỏ qua. Phương án "Best case is O(nlogn) , the worst case is O(n^2)" là mô tả của quicksort, nơi chốt lệch làm cây đệ quy suy biến thành n mức; mergesort không chọn chốt nên không gặp cảnh đó. Phương án "The best case is O(n), and the worst case is O(n^2)" ghép trường hợp tốt của insertion sort với trường hợp xấu của quicksort, không khớp bước nào của mergesort.
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