为什么以下c ++代码的时间复杂度为O(n ^ n)? [英] Why the time complexity of the following c++ code is O(n^n)?

问题描述

这是此lettcode问题的蛮力解决方案:

This is the brute force solution of this lettcode problem: https://leetcode.com/articles/best-time-to-buy-and-sell-stock-ii/, and I don't get why the time complexity if O(n^n) as claimed. Can anyone explain and walk me through it, thanks!

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;
    }
}

推荐答案

由于最内层循环中有一个递归调用，因此扩展树如下图所示

Since there is a recursive call in the innermost loop the expansion tree will look like below

                                        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)个总操作.

On first row there are n-1 or O(n) operations, on second row there are (n-1)+(n-2)+...+1 = n*(n-1)/2 or O(n^2) operations. Similarly on third row there are O(n^3) operations. The tree height/depth is n. So continuing this way there will be O(n^n) total operations.

这篇关于为什么以下c ++代码的时间复杂度为O(n ^ n)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！