这是此lettcode问题的蛮力解决方案：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;
}
}
由于在最内部的循环中有一个递归调用，因此扩展树如下所示
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)全部操作。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句