1.只进行一次递归调用

image.png
image.png

举例

1.求和
image.png
2.求pow
image.png

2.递归中进行多次递归调用

image.png
image.png
指数级的算法非常慢，当n=20，就已经是百万数量级的运算了。因此需要进行剪枝或者转化为dp。
那为什么归并排序的时间复杂度是O（NlogN）而不是指数级别呢？
image.png
因为每一层的数据规模是越来越小的，每一层的总和才是N，而树的高度是logN