java - Java中递归算法的优化

Question

背景

我有一组有序的数据点存储为 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()已经为这些参数计算了它只是返回以前的结果，但这并没有解决固有的复杂性问题。关于重复计算，我是否遗漏了什么，或者这个算法的复杂性是不可避免的吗？

Answer 1

您还需要记住前 2 个参数的 f(第 3 个参数总是通过，因此您无需担心)。这会将代码的时间复杂度从 O(2^n) 降低到 O(n)。