背景
我有一组有序的数据点存储为 TreeSet<DataPoint>
.每个数据点都有一个 position
和一个 Set
的 Event
对象 ( HashSet<Event>
)。
有 4 个可能 Event
对象 A
, B
, C
, 和 D
.每个DataPoint
有其中 2 个,例如A
和 C
, 除了第一个和最后一个 DataPoint
集合中的对象,具有 T
大小为 1。
我的算法是求一个新DataPoint
的概率Q
在位置x
有Event
q
在这个集合中。
我通过计算一个值 S
来做到这一点对于这个数据集,然后添加 Q
到集合和计算S
再次。然后我划分第二个 S
由第一个分离出新的概率DataPoint
Q
.
算法
S
的计算公式是:
http://mathbin.net/equations/105225_0.png
在哪里
http://mathbin.net/equations/105225_1.png
http://mathbin.net/equations/105225_2.png
为了 http://mathbin.net/equations/105225_3.png
和
http://mathbin.net/equations/105225_4.png
http://mathbin.net/equations/105225_5.png是一个昂贵的概率函数,只依赖于它的参数而不依赖于其他(和 http://mathbin.net/equations/105225_6.png ),http://mathbin.net/equations/105225_7.png是最后DataPoint
在集合(右手节点)中,http://mathbin.net/equations/105225_8.png是第一个DataPoint
(左手节点),http://mathbin.net/equations/105225_9.png是最右边的 DataPoint
那不是节点,http://mathbin.net/equations/105225_10.png是 DataPoint
, http://mathbin.net/equations/105225_12.png是Set
DataPoint
的事件.
所以 Q
的概率与 Event
q
是:
http://mathbin.net/equations/105225_11.png
实现
我是这样用 Java 实现这个算法的:
public class ProbabilityCalculator {
private Double p(DataPoint right, Event rightEvent, DataPoint left, Event leftEvent) {
// do some stuff
}
private Double f(DataPoint right, Event rightEvent, NavigableSet<DataPoint> points) {
DataPoint left = points.lower(right);
Double result = 0.0;
if(left.isLefthandNode()) {
result = 0.25 * p(right, rightEvent, left, null);
} else if(left.isQ()) {
result = p(right, rightEvent, left, left.getQEvent()) * f(left, left.getQEvent(), points);
} else { // if M_k
for(Event leftEvent : left.getEvents())
result += p(right, rightEvent, left, leftEvent) * f(left, leftEvent, points);
}
return result;
}
public Double S(NavigableSet<DataPoint> points) {
return f(points.last(), points.last().getRightNodeEvent(), points)
}
}
所以求Q
的概率在x
与 q
:
Double S1 = S(points);
points.add(Q);
Double S2 = S(points);
Double probability = S2/S1;
问题
就目前的实现情况而言,它严格遵循数学算法。然而,这在实践中并不是一个特别好的主意,因为 f
每个 DataPoint
调用自己两次.所以对于 http://mathbin.net/equations/105225_9.png , f
被调用两次,然后为 n-1
f
之前的每次调用都会再次调用两次,依此类推。这导致了 O(2^n)
的复杂性考虑到可能有超过 1000 个 DataPoints
,这非常糟糕在每个Set
.因为p()
独立于它的参数之外的所有内容我已经包含了一个缓存函数,如果p()
已经为这些参数计算了它只是返回以前的结果,但这并没有解决固有的复杂性问题。关于重复计算,我是否遗漏了什么,或者这个算法的复杂性是不可避免的吗?
最佳答案
您还需要记住前 2 个参数的 f
(第 3 个参数总是通过,因此您无需担心)。这会将代码的时间复杂度从 O(2^n) 降低到 O(n)。
关于java - Java中递归算法的优化,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11968187/