Большая сложность создания рекурсивного троичного дерева с шириной k - PullRequest
Новая
       22

Большая сложность создания рекурсивного троичного дерева с шириной k

1 голос
/ 22 мая 2019

Я хочу знать всю сложность моего алгоритма.

Я пытаюсь оптимизировать прибыль от покупки акций на каждом листе дерева из списка цен.Для каждой цены мы можем сделать 3 варианта, купить одну единицу, продать одну единицу или ничего не делать.Существует ограничение, которое ограничивает количество акций, которые мы можем иметь за один раз, например, 0 акций минимум и 5 акций максимум, поэтому, если у нас есть список из 20 цен, какие действия я должен предпринять, чтобы максимизировать прибыль и закончить с 3 акциями.

Для этой задачи я создал этот рекурсивный метод: 

    def _next_price_unit(self, load, prices, money=0, depth=0):
"""Recursive dynamic programming step
            Tree load has a depth index where the max depth is the length of the
            prices array while load index is the level of current stocks.The
            tree load will return the best revenue at that depth and stock load."""

        if len(prices) is depth:  # Max depth, stop condition
            return
        if self.tree_load[depth][load] < money:  # No change in load
            self.tree_load[depth][load] = money
            self._next_price_unit(load, prices, money, depth + 1)

         #Check load in stock boundaries and money increases at -1 or +1 load
        if load - 1 >= self.stock_min\
                and money + prices[depth] > self.tree_load[depth][load - 1]:
            self.tree_load[depth][load - 1] = money + prices[depth]  # Sell
            self._next_price_unit(load - 1, prices, money + prices[depth],
                                  depth + 1)

        if load+1 <= self.stock_max\
                and money - prices[depth] > self.tree_load[depth][load+1]:
            self.tree_load[depth][load + 1] = money - prices[depth]  # Buy
            self._next_price_unit(load + 1, prices, money - prices[depth],
                                  depth + 1)

Без ограничения минимального и максимального запаса я знаю, что сложность троичного дерева будет O (3 ^ n), и яЯ знаю, что это может быть решено в O (k * n), если я использую динамическое программирование, сравнивая значения на каждом уровне глубины и затем продвигаясь вперед.Этот алгоритм будет идти до конца глубины, затем назад, вперед, назад назад и так далее.

Может кто-нибудь сказать мне, в чем сложность?Я не могу разобраться с этим.

...