python - 贪心递归算法的时间复杂度

Question

我编写了一个贪婪递归算法来查找进行给定更改的最小硬币数量。现在我需要估计它的时间复杂度。由于该算法根据相同的 i (n * n) 嵌套了“if”，内部 block 将递归调用减半 (log(2)n)，我相信正确的答案可能是 O(n*log(n) )，由以下计算得出:

n * log2(n) * O(1)

请告诉我您对我的分析是否正确的想法，并随时对我的贪婪递归算法提出改进建议。

这是我的递归算法:

coins = [1, 5, 10, 21, 25]
coinsArraySize = len(coins)
change = 63
pickedCoins = []

def findMin(change, i, pickedCoins):              
    if (i>=0):
        if (change >= coins[i]):               
           pickedCoins.append(coins[i])
           findMin(change - coins[i], i, pickedCoins)
        else:           
           findMin(change, i-1, pickedCoins)
findMin(change, coinsArraySize-1, pickedCoins)

Answer 1

每次递归调用都会减少至少 1 的变化，并且没有分支(也就是说，你的递归树实际上是一条直线，因此实际上不需要递归)。你的运行时间是O(n)。