Tôi đang cố gắng hiểu các yêu cầu về không gian cho một Mergesort, O (n).
Tôi thấy rằng các yêu cầu về thời gian về cơ bản là, mức độ (logn) * hợp nhất (n) sao cho tạo (n log n).
Bây giờ, chúng tôi vẫn phân bổ n cho mỗi cấp độ, trong 2 mảng khác nhau, trái và phải.
Tôi hiểu rằng chìa khóa ở đây là khi các hàm đệ quy trả về không gian bị deallocated, nhưng tôi không thấy nó quá rõ ràng.
Bên cạnh đó, tất cả thông tin tôi tìm thấy, chỉ cần nêu rõ không gian được yêu cầu là O (n) nhưng không giải thích được.
Bất kỳ gợi ý nào?Các yêu cầu về không gian của một sắp xếp hợp nhất
function merge_sort(m)
if length(m) ≤ 1
return m
var list left, right, result
var integer middle = length(m)/2
for each x in m up to middle
add x to left
for each x in m after middle
add x to right
left = merge_sort(left)
right = merge_sort(right)
result = merge(left, right)
return result
EDIT Ok, nhờ @Uri, đây là lừa
Những gì tôi không nhìn thấy ở đầu là thời gian mà chỉ cho biết thêm, trong khi bộ nhớ cộng và trừ, vì vậy số tiền tối đa thời gian là lúc kết thúc thực hiện, nhưng số lượng tối đa của bộ nhớ là ở dưới cùng của ngăn xếp đệ quy.
Vì vậy, nếu chúng ta tiếp tục thêm n + n/2 + n/4 + n/8 .... không quan trọng số lần chúng ta thêm vào, nó sẽ không bao giờ lớn hơn 2n và khi chúng ta đạt đến đáy stack đệ quy và bắt đầu đi lên, chúng tôi không giữ bộ nhớ được sử dụng cho các chi nhánh trước đó, do đó, tại tối đa, 2n sẽ là số lượng bộ nhớ được sử dụng, O (n).
@Arkaitz: "Triển khai nhiều nhất" bao gồm triển khai bạn đã đăng. – Brian
Tôi đã đăng những gì tôi hiểu bây giờ, sửa tôi nếu sai xin vui lòng. –
Bạn hiểu chính xác. Vấn đề là với mã giả, Nó dễ dàng hơn để hình dung điều khiển (và do đó thời gian phức tạp) hơn là nội dung của ngăn xếp cuộc gọi. – Uri