Оптимизация рекурсивного алгоритма в Java

Фон

У меня есть упорядоченный набор точек данных, хранящихся как TreeSet. Каждая точка данных имеет positionи Setиз Eventобъектов (HashSet)..

Существует 4 возможных Eventобъекта A, B, Cи D. Каждый DataPointимеет 2 из них, например. Aи C, за исключением первого и последнего DataPointобъектов в наборе, которые имеют Tразмера 1.

Мой алгоритм состоит в том, чтобы найти вероятность новогоDataPointQв позиции x, имеющейEventqв этом наборе.

Я делаю это, вычисляя значение Sдля этого набора данных, затем добавляя Qк набору и снова вычисляя S. Затем я делю второе Sна первое, чтобы выделить вероятность новогоDataPointQ.

Алгоритм

Формула для вычисления 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приEventqэто:

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 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 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-1fвызывается еще дважды для каждого из предыдущих вызовов, и так далее и тому подобное. Это приводит к сложности O(2^n), что довольно ужасно, учитывая, что в каждом Setможет быть более 1000 DataPoints. Поскольку p()не зависит ни от чего, кроме своих параметров, я включил функцию кэширования, в которой, если p()уже было вычислено для этих параметров, она просто возвращает предыдущий результат, но это не решает проблему внутренней сложности. Я что-то упустил здесь в отношении повторных вычислений, или сложность в этом алгоритме неизбежна?