我想知道我算法的复杂性。你知道吗
我正试图从一张价格表中的每一片树叶上购买股票,以优化利润。对于每一个价格,我们可以做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)来解决。 这个算法会一直到深度端,然后向后,向前,向后等等。你知道吗
有人能告诉我什么是复杂性吗?我想不通。你知道吗
目前没有回答
相关问题 更多 >
编程相关推荐