我们可以看出这是一个递归程序，并且每一次都会调用两次函数。我们可以画出递归搜索树。 有图可知，每一层的节点数都是按2的次方一次递增上去的，1，2，4，8，16......。每次任务平摊给子节点，当任务总数为1或者0的时候就会返回。由于任务每一层均二分，则一共有 $\log_2n$层 所以底部节点的个数为 $2^{\log_2n}$(n) 。一次总节点数为 1 + 2 + 4 + ... + n。可以看出这是一个等比数列，公比为2。设S = 1 + 2 + 4 + ... + n,则2S = 2 + 4 + 8 + ... + 2n,所以S = 2S - S = 2n - 1。 而每个节点都是O(1)的复杂度(只有两个if和一条return)。所以总复杂度就是节点总数即O(n)。