Select the most correct statement:
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: "The complexity of insertion sort is O(n^2), in the best case it is O(n).". Sắp xếp chèn lấy từng phần tử rồi dịch ngược về vị trí đúng trong phần đã sắp, và vòng lặp trong dừng ngay khi gặp phần tử nhỏ hơn hoặc bằng. Khi mảng đã sắp sẵn, mỗi phần tử chỉ so đúng một lần với phần tử liền trước rồi dừng, tổng n-1 phép so sánh và không có phép dịch nào, tức O(n); khi mảng sắp ngược, phần tử thứ i phải dịch qua i phần tử, tổng khoảng n(n-1)/2 phép, tức O(n^2). Vì vậy "In all cases the insertion sort is O(n^2)." sai vì nó bỏ qua trường hợp mảng đã sắp, nơi điều kiện dừng sớm cắt hẳn vòng trong; "The complexity of insertion sort is O(nlog n), in the best case it is O(n)." sai vì O(nlog n) là cấp của những thuật toán chia đôi dữ liệu như trộn hay vun đống, còn chèn thì dịch tuần tự nên trường hợp xấu là bình phương; "The complexity of insertion sort is O(n^2), in the best case it is O(nlog n)." sai vì trường hợp tốt nhất còn nhanh hơn thế, chỉ cần n-1 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