如果您有一个包含各种数字的正方形区域，每个递归关系的结果是什么？：
T(n) = 3T(n/2) + c 和 T(n) = 2T(n/2) + cn
我知道第一个应该导致四分区，第二个应该导致二进制分区，但是我不能直观地理解为什么会这样。为什么我们在第一种情况下进行 3 次递归调用，在第二种情况下进行 2 次递归调用？为什么 +c 或 +cn 会影响我们正在解决的问题？
问问题
418 次
1 回答
1
我想这就是你要找的
http://leetcode.com/2010/10/searching-2d-sorted-matrix-part-ii.html
如果您的问题只是关于递归解释，我建议阅读使用递归树和主方法解决递归
http://courses.csail.mit.edu/6.006/spring11/rec/rec08.pdf
这解释了第二次递归和方法。基本上，您将拥有一个高度 (lgn) 的递归树，并且每个级别的成本等于 n。
在第一个中，递归树将具有树中节点数量顺序的运行时间。高度仍为 lgn，但每个级别的成本为 3^h * c。对此的总结会给你带来复杂性
于 2013-02-27T22:03:40.633 回答