Сложность рекурсивного вызова внутри 2 циклов for - PullRequest
Новая
       53

Сложность рекурсивного вызова внутри 2 циклов for

3 голосов
/ 01 августа 2020 

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))

После этого, как чтобы решить это рекуррентное отношение с двумя переменными?

1 Ответ

0 голосов
/ 02 августа 2020

вложенный l oop означает n 2 , и если вы вычислите два рекурсивных уравнения, вы найдете:

  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 2 {T (n-1) + T (n-1)} = n 2 {2T (n-1)} для {2T (n-1)} сложность O ( 2 n ), а теперь умножьте его на n 2 , но поскольку n 2 намного меньше, чем 2 n , мы игнорируем их и сложность стоит: O (2 n )

...