2020年5月17日 下午3:49
花花酱 Time/Space Complexity of Recursion Functions SP4 – Huahua’s Tech Road
总结：
- 排列和组合的思维本质：递归。递归代表着：递推表达式
- 排列和组合总是放在一起讲，我觉得其实这就是两个完全不相关的问题
- 在combination中，T(n) = T(n-1) + T(n-2) + T(n-3) + …. + T(1)，这个式子的语义是：我们将一个n个元素可以有多少种组合的问题T(n)，拆解为(n-1) n(n-2)…n(1)的子问题和。
- Eg：[1,2,3] 我们就拆解成：
- 当使用3个元素时，有少种组合数
- 当使用2个元素时，有多少种组合数
- 当使用1个元素时，有多少种组合数
- Eg：[1,2,3] 我们就拆解成：
- 在permutation中，我们将问题拆解成T(n) = n * T(n-1)
- 语义：在一个排列的第一个位置上，有n种放置元素方法，在每种放置下，后面还有T(n-1)种排列方式
- 我们将其加起来，就变成了T(n) = n * T(n-1)
- 解决排列和组合问题的思路对比：
- 区别：
- 组合问题的解决更像是对问题本身的分类
- 排列问题的解决更像是一步步的过程模拟
- 相同：
- 不论是组合的分类，还是排列的模拟过程，在编程中都可以通过递归这个编程技巧来作为实现方式
- 因为，都涉及相同的子问题。
- 区别：
- 理解了排列和组合的本质是递归以外，我们在真正解决问的时候还依靠于一个技巧：递归树。递归树的优势是形象，我们再写代码的时候，如果脑子里是按照递归树来写，就很容易分析边界等条件，所以说递归树这点要比直接的使用递归表达式来写更好，递归表达式更适合问题是一个问：有多少种组合的结果，这样直接数字型的答案：
- 递归树的优点：
- 很容易分析边界等条件
- 在遇到题目扩展的时候，更容易进行扩展
- 递推表达式的优点：
- 在计算复杂度的时候更加方便
- 递归树的优点：