Select the most correct statement about the complexity of insertion 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: "The best case is O(n), and the worst case is O(n^2)". Sắp xếp chèn lấy từng phần tử rồi đẩy nó lùi về chỗ đúng trong phần đã sắp. Nếu mảng đã sắp sẵn, mỗi phần tử chỉ cần một phép so sánh với phần tử liền trước là dừng, tổng cộng n trừ 1 phép so sánh nên chi phí tuyến tính. Nếu mảng sắp ngược, phần tử ở vị trí thứ i phải lùi qua cả i phần tử trước nó, tổng là 1 cộng 2 cộng tới n trừ 1, xấp xỉ n bình phương chia 2 nên là bậc hai. "Both best and worst cases are O(n^2)" bỏ mất tính thích nghi với dữ liệu gần sắp, vốn là lý do người ta dùng sắp xếp chèn cho mảng nhỏ hoặc gần như đã sắp. "The best case is O(n), and the worst case is O(nlogn)" gán cho nó cận xấu nhất của sắp xếp trộn hay vun đống, trong khi chèn không chia đôi dữ liệu nên không đạt được n log n. "The best case is O(nlogn), and the worst case is O(n^2)" đặt cận tốt nhất quá cao, vì với mảng đã sắp số phép so sánh chỉ là n trừ 1.
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