斯坦福算法设计和分析_3. 分治算法
本文预计阅读时间4分钟,在读的过程中你需要带着以下问题:
扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄
- 分治算法的基本步骤
- 逆序对计数是如何使用分治算法来解决问题的
- 为什么MergeSort排序法可以自然的算出逆序对数目
- 把输入划分成更小的子问题。
- 递归的治理子问题。
- 把子问题的解决方案组合到一起,形成原始问题的解决方案。
- 第1种就是逆序对 i 和 j 都位于数组的左半部分,就是下标 i 和 j 是小于等于n/2的
- 第2种情况是逆序对 i 和 j 位于数组的右半部分
- 第3种情况是逆序对 i 位于左半部分 j 位于右半部分,以上是伪代码。
更多精彩