Làm cách nào để xác định chiều cao của cây đệ quy, được xây dựng khi xử lý thời gian chạy lặp lại? Nó khác với việc xác định chiều cao của cây thông thường như thế nào?Làm thế nào để xác định chiều cao của một cây đệ quy từ một mối quan hệ lặp lại?
alt text http://homepages.ius.edu/rwisman/C455/html/notes/Chapter4/ch4-9.gif
chỉnh sửa: xin lỗi, tôi có nghĩa là để thêm làm thế nào để có được chiều cao của cây đệ quy từ mối quan hệ tái phát.
Chiều cao của cây đệ quy phụ thuộc vào thuật toán đệ quy được đề cập. Không phải tất cả các thuật toán phân chia và chinh phục đều có chiều cao cây đồng nhất, cũng giống như không phải tất cả các cấu trúc cây đều có chiều cao đồng nhất. Nếu bạn không thể xác định chiều cao tối đa có thể của thuật toán, hoặc nếu bạn cần tính chiều cao thực tế của cây tại thời gian chạy, bạn có thể sử dụng biến toàn cục cho hàm đệ quy, tăng nó khi nhập vào hàm và giảm nó khi thoát khỏi chức năng. Biến này sẽ cho biết mức độ hiện tại của thủ tục đệ quy. Nếu cần, bạn có thể duy trì giá trị lớn nhất của biến này trong biến thứ hai.
Thứ nhất, nếu đây là câu hỏi về bài tập về nhà, vui lòng đánh dấu câu hỏi như vậy. Những hình ảnh bạn liên kết ngụ ý rằng bạn đang ở trong CS 455, với Giáo sư Wisman. :)
Gợi ý chính tôi sẽ đưa ra là: Chiều cao của cây rõ ràng được xác định khi bạn đến "lá". Các lá của một cây mô hình hóa mối quan hệ lặp lại của một hàm là trường hợp cơ bản. Do đó, tôi sẽ xem xét việc xem "nhanh" N có thể co lại như thế nào.
Đây không phải là bài tập về nhà:) Nghiên cứu cá nhân. Hình ảnh tôi liên kết đến là hình ảnh có liên quan nhất trên google. Nên đã xóa trước đó, xin lỗi! – Chris
Rất tiếc, đã thêm nhận xét quá sớm. Câu trả lời của bạn chắc chắn có ý nghĩa. Tuy nhiên, nó không phải là thường là trường hợp mà bạn có thể làm theo lá tất cả các con đường xuống. Việc tạo ra một vài nhánh đầu tiên là tầm thường. Nó từ đó mà tôi có chút bối rối :) – Chris
Nếu tái diễn ở dạng T (n) = aT (n/b) + f (n) thì độ sâu của cây là bệ b của n.
Ví dụ, 2T (n/2) + n lặp lại sẽ có cây có độ sâu lg (n) (log base 2 of n).
Chụp từ bum của tôi ở đây, nhưng tôi không thấy sự khác biệt. Tại sao bạn nghĩ có sự khác biệt? Trong tóm tắt, chúng là cả hai cây ... –
xem câu trả lời của tôi ở đây: http://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly/13093274#13093274 – 2cupsOfTech