The complexity of quick 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)". Quicksort phân hoạch mảng quanh một chốt rồi gọi đệ quy hai phần; khi chốt chia tương đối đều, cây đệ quy sâu khoảng log n mức và mỗi mức tốn khoảng n phép so sánh cho các bước phân hoạch, nên tổng chi phí là n log n, và đó cũng là độ phức tạp trung bình thường được dùng để gọi tên thuật toán. "O(log n)" là chi phí của một lần tìm nhị phân hay một lần đi từ gốc xuống lá, nhỏ hơn cả việc đọc hết mảng nên không thể là chi phí sắp xếp. "O(n)" là chi phí của đúng một lượt phân hoạch, mới là một mức trong cây đệ quy. "O(n^2)" đúng ở trường hợp xấu nhất, khi chốt luôn rơi vào phần tử nhỏ nhất hoặc lớn nhất, chẳng hạn mảng đã sắp sẵn mà chốt lấy ở đầu, làm đệ quy sâu tới n mức; đó là cận xấu nhất chứ không phải độ phức tạp vẫn được nêu cho quicksort.
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