The complexity of heap sort is
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: "O(nlog n)". Sắp xếp vun đống làm hai việc: dựng đống từ mảng, rồi lặp n lần lấy phần tử lớn nhất ở gốc đổi về cuối và vun lại phần còn lại. Mỗi lần vun lại chỉ đi từ gốc xuống theo một đường tới lá, dài nhất là log n bước, nên n lần lấy ra tốn n log n; phần dựng đống còn nhanh hơn thế. Đáng nhớ là cận này đúng cho cả trường hợp tốt nhất và xấu nhất, vì chiều cao đống không phụ thuộc dữ liệu. "O(log n)" là chi phí của đúng một lần vun lại, mới là một trong n bước. "O(n)" là chi phí đọc hết mảng một lần, cũng là chi phí dựng đống, chưa tính n lần lấy phần tử lớn nhất. "O(n^2)" là cận xấu của những thuật toán đổi chỗ các phần tử lân cận như sắp xếp chèn hay nổi bọt; vun đống không rơi xuống mức đó vì nó luôn tìm được phần tử lớn nhất trong log n bước.
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