g******y
发帖数: 143 | 1 Given a decision tree, and lower & upper bounds for each dimension of a d-
dimension space. Find the maximum volume of the d-dimension space and its
lower and upper bounds. 大家有没有优于O(n)的解法？
这题有点绕. 举个两维的例子:
initial range for d0 is (0,10), d1 is (0,10)
Decision tree
idx=1,split=4
/ \
/ \
null idx=0,split=2
d1
10 | |
| |
| |
4 |___|_______________
|
|
|___________________
0 2 10 d0 | g******y
发帖数: 143 | | j*****8
发帖数: 3635 | 3 没看懂
d-
【在 g******y 的大作中提到】
: 格式乱了
| m*****7
发帖数: 2 | 4 当d0没有子结点的时候，d0是取<2还是>2的区间？ | m*****7
发帖数: 2 | 5 好像明白了，例子里一共有三个2d space. volume最大的是d1 > 4, d0 > 2那个。这种
解法的worst case是O(n), 需要遍历所有结点求解。
但是，在例子里面比如根结点的左子数为空，idx=1,split=6的话，就不需要遍历右子
树了。想不到更好的解法了。 | x*****z
发帖数: 15 | 6 层遍历到leaf之前都没法排除某个子树，好像没有比O(n)更好的吧。 |
|
