algorithm - 2个for循环内递归调用的时间复杂度

Question

int maxProfit(int price[], int start, int end) 
{ 
  
    // If the stocks can't be bought 
    if (end <= start) 
        return 0; 
  
    // Initialise the profit 
    int profit = 0; 
  
    // The day at which the stock 
    // must be bought 
    for (int i = start; i < end; i++) { 
  
        // The day at which the 
        // stock must be sold 
        for (int j = i + 1; j <= end; j++) { 
  
            // If byuing the stock at ith day and 
            // selling it at jth day is profitable 
            if (price[j] > price[i]) { 
  
                // Update the current profit 
                int curr_profit = price[j] - price[i] 
                                  + maxProfit(price, start, i - 1) 
                                  + maxProfit(price, j + 1, end); 
  
                // Update the maximum profit so far 
                profit = max(profit, curr_profit); 
            } 
        } 
    } 
    return profit; 
} 

maxProfit 的时间复杂度是多少？

在我看来，递归关系是:

T(0,n) = n^2*(T(0,i) +  T(j,n))

在此之后，如何解决这个 2 变量递归关系？

Answer 1

嵌套循环意味着 n²，如果你计算两个递归方程，你会发现:

1. 第一个递归关系如果 n = 5 那么它将运行 1,2,3,4次。所以，T(n) = T(1)+T(2)+T(3)+....+T(n-1)
2. 第二个递归关系如果 n = 5 那么它将运行 4,3,2,1次。所以，T(n) = T(n-1)+T(n-2)+.....+T(1)

所以 T(n) = n²{ T(n-1)+T(n-1) }= n²{ 2T(n-1)} for {2T(n-1)} 复杂度为 O(2ⁿ) 现在乘以 n² 但由于 n² 远小于 2ⁿ 所以我们忽略它们并且复杂度为:O(2ⁿ)