checkIfBalanced() phương pháp trong mã dưới đây trả về giá trị true nếu cây được cân bằng và sai khác. Tuy nhiên trong mỗi đệ quy nó tạo ra đối tượng TreeData. Trong sự phức tạp của không gian ý kiến của tôi là O (1) như sau mỗi khung ngăn xếp được xuất hiện, tham chiếu của đối tượng được tạo trên khung ngăn xếp đó bị mất và thu thập rác. Tôi có đúng không?Sự phức tạp của không gian khi tạo đối tượng trên đệ quy
Xin lưu ý:
Tôi không tìm kiếm gợi ý để cải thiện/thay đổi mã của tôi. Ví dụ sau về mã được thiết kế riêng để đặt câu hỏi của tôi.
Ngoài ra,
please ignore space-complexity adding stack frames. Tôi đang tìm kiếm sự phức tạp về không gian của các đối tượng 'TreeData' số được tạo. Có vẻ với tôi rằng tại bất kỳ thời điểm nào, sẽ chỉ có 3 đối tượng TreeData. Đó là những gì tôi muốn xác minh. Cảm ơn.
private static class TreeData {
private int height;
private boolean isBalanced;
TreeData(int height, boolean isBalanced) {
this.height = height;
this.isBalanced = isBalanced;
}
}
public boolean checkIfBalanced() {
if (root == null) {
throw new IllegalStateException();
}
return checkBalanced(root).isBalanced;
}
public TreeData checkBalanced(TreeNode node) {
if (node == null) return new TreeData(-1, true);
TreeData tdLeft = checkBalanced(node.left);
TreeData tdRight = checkBalanced(node.right);
if (tdLeft.isBalanced && tdRight.isBalanced && Math.abs(tdLeft.height - tdRight.height) <= 1) {
return new TreeData(Math.max(tdLeft.height, tdRight.height) + 1, true);
}
return new TreeData(Math.max(tdLeft.height, tdRight.height) + 1, false);
}
để số lượng đối tượng của TreeData trong bộ nhớ sẽ chỉ là 1 - vì vậy, nếu tôi "bỏ qua không gian ngăn xếp" , độ phức tạp sẽ là O (1)? Các đối tượng đó có bị thu gom rác nếu các tham chiếu được bật lên không? – JavaDeveloper
@ JavaDeveloper- 1. Nếu bạn bỏ qua không gian ngăn xếp và chỉ xem xét tham chiếu hiện tại, thì sẽ chỉ có 1 đối tượng TreeData hoạt động. 2. *** Có thể/Có thể không ***, ngay sau khi ngăn xếp bật ra tất cả các nút, các đối tượng có thể HOẶC có thể không được thu thập rác, nó phụ thuộc vào JVM để đoán liệu chúng sẽ được tái sử dụng trong Tương lai. Đối với surity, bạn cần phải làm điều đó bằng tay bằng cách thiết lập những đối tượng để 'null' để họ có thể nhận được rác thu thập. Trả lời câu trả lời (đặc biệt là câu trả lời của Stephen C) -> http://stackoverflow.com/questions/27781116/garbage -collection-in-java-với-đệ quy-chức năng –