这是此lettcode问题的蛮力解决方案: leetcode/articles/best-time-to-buy-and-sell-stock-ii/，而且我不明白为什么如果O(n ^ n ).谁能解释一下并向我介绍，谢谢！
This is the brute force solution of this lettcode problem: leetcode/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)?
发布评论