19
Độ phức tạp về thời gian đi qua của cây là gì, tôi chắc chắn nó phải rõ ràng nhưng bộ não nghèo của tôi không thể hoạt động ngay bây giờ.Độ phức tạp của thời gian đi qua cây là gì?
A
Trả lời
20
Nó phụ thuộc vào loại truyền tải bạn đang thực hiện và thuật toán, nhưng thông thường nó sẽ là O (n) trong đó n là tổng số nút trong cây. Việc thực hiện đệ quy chuẩn về chiều sâu đầu tiên truyền tải, sẽ tiêu thụ bộ nhớ (trên stack) theo thứ tự mức sâu nhất, mà trên một cây cân bằng nó sẽ là log (n).
+0
Điều này đúng với cây n-ary? Tôi có một cấu trúc dữ liệu là một cây có độ sâu tối đa 4 và đi qua nó, bạn tôi đang sử dụng 3 cho vòng lặp, và nói thuật toán của anh ta chạy trong thời gian 'O (n^3)', nhưng tôi tin nó đang chạy trong ' n' thời gian, 'n' là tổng số nút trong cây – Nicholas
+4
@Nocholas, bạn là chính xác và bạn của bạn là sai. Nó là O (n). – Uri
1
Nó sẽ không chỉ là n cho một cây có các nút n?
Bạn truy cập từng lần nghỉ một lần, phải không? Vì vậy, tôi muốn nói nó là tuyến tính.
+0
Tôi đoán nó phải là cây có "n nút" và không phải là "n lá". – aamadmi
+0
Bạn đúng, sai terminoligy :) – Nanne
+0
@Nanne Với thuật toán đúng nó thực sự là một phức tạp tuyến tính trong thời gian (truy cập mỗi nút một lần), nhưng nó vẫn có thể không có một sự phức tạp tuyến tính trong không gian. Giống như sử dụng ngăn xếp. – Tim
Các vấn đề liên quan
- 1. Độ phức tạp thời gian của random.sample
- 2. Độ phức tạp về thời gian đếm
- 3. Độ phức tạp của OrderedDictionary là gì?
- 4. Độ phức tạp thời gian của thuật toán Prim
- 5. Độ phức tạp thời gian của hàm này trong sơ đồ là gì?
- 6. Độ phức tạp về thời gian của việc xóa một nút trong cây nhị phân
- 7. Độ phức tạp của thời gian nguyên trong Haskell
- 8. Độ phức tạp thời gian chạy của câu lệnh switch là gì?
- 9. Độ phức tạp của thời gian A * là gì và nó bắt nguồn như thế nào?
- 10. Độ phức tạp thời gian chạy của các hàm danh sách python là gì?
- 11. Độ phức tạp về thời gian của system.out.println
- 12. Độ phức tạp về thời gian của erlang dict
- 13. Độ phức tạp về thời gian đối với java ArrayList
- 14. Độ phức tạp về thời gian tra cứu HTML DOM là gì
- 15. Độ phức tạp về thời gian được đặt trong Java
- 16. Độ phức tạp của set_intersection trong C++ là gì?
- 17. Độ phức tạp của chức năng nhật ký là gì?
- 18. Đặt thời gian và tốc độ phức tạp
- 19. Thời gian phức tạp của phương pháp HashMap
- 20. Thời gian phức tạp của Sieve of Eratosthenes thuật toán
- 21. Độ phức tạp của ưu tiênQueue addAll()
- 22. Độ phức tạp về thời gian của thuật toán đồ thị độ sâu đầu tiên
- 23. Độ phức tạp thời gian của một kích thước() gọi trên một LinkedList trong Java là gì?
- 24. Độ phức tạp thời gian tra cứu của HashSet <T> (IEqualityComparer <T>) là gì?
- 25. Thời gian phức tạp của phương pháp JavaConverters asScala
- 26. Độ phức tạp của HashMap.containsValue() trong java là bao nhiêu?
- 27. Độ phức tạp về thời gian của chuỗi con của Java()
- 28. Độ phức tạp về thời gian của thuật toán của Fleury
- 29. Độ phức tạp của hàm find() trong std :: map?
- 30. Độ phức tạp về thời gian chứa (Object o), trong ArrayList của các đối tượng
Đó là nghệ thuật tuyến tính của lập trình Vol 1 trang 326 – new299
Đó có phải là nghệ thuật lập trình của Knuth không? Tôi đang cố gắng để tìm thấy điều này để cung cấp cho một người bạn một ví dụ tốt cho một cây n-ary đó là tuyến tính. – Nicholas
yes "Nghệ thuật lập trình máy tính" của Knuth – new299