1

我想知道我的算法的复杂性。

我正在尝试优化从价格列表中购买每棵树的每一片叶子的股票的利润。对于每个价格，我们可以做 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) 中解决深度，然后继续前进。这个算法会一直到深度结束，然后是向后，向前，向后向后等等。

有人能告诉我什么是复杂性吗？我无法理解它。

4

0 回答 0