Почему временная сложность следующего кода на C ++ равна O (n ^ n)?

Question

Это грубое решение этой проблемы: https://leetcode.com/articles/best-time-to-buy-and-sell-stock-ii/, и я не понимаю, почему сложность времени, если O (n ^ n), как заявлено. Может кто-нибудь объяснить и провести меня через это, спасибо!

class Solution {
    public int maxProfit(int[] prices) {
        return calculate(prices, 0);
    }

    public int calculate(int prices[], int s) {
        if (s >= prices.length)
            return 0;
        int max = 0;
        for (int start = s; start < prices.length; start++) {
            int maxprofit = 0;
            for (int i = start + 1; i < prices.length; i++) {
                if (prices[start] < prices[i]) {
                    int profit = calculate(prices, i + 1) + prices[i] - prices[start];
                    if (profit > maxprofit)
                        maxprofit = profit;
                }
            }
            if (maxprofit > max)
                max = maxprofit;
        }
        return max;
    }
}

Answer 1

Поскольку во внутренней l oop имеется рекурсивный вызов, дерево расширения будет выглядеть следующим образом:

                                        0
                ---------------------------------------------------------
                1                               2   ..                  n
    ------------------------            ---------------------          
    2           3  ..      n            3           4   ..  n   
----------  -------------       ----------   ------------
3   4 .. n  4   5  ..   n       4   5 .. n   5  6   ..  n
                                       ...

В первой строке есть операции n-1 или O(n), во второй строке (n-1)+(n-2)+...+1 = n*(n-1)/2 или O(n^2) операций. Аналогичным образом в третьем ряду выполняются операции O(n^3). Высота / глубина дерева n. Таким образом, продолжая таким образом, будет O(n^n) всего операций.