如何计算多方法循环调用的递归函数的时间复杂度Big O？

多个函数互相调用的递归场景，通用计算步骤如下：

• 先为每个函数单独定义时间复杂度函数，比如用T1(n)表示输入规模为n时F1的时间开销，T2(n)表示输入规模为n时F2的时间开销
• 根据每个函数的执行逻辑，列出对应的递推关系式，需要覆盖三个要素：函数内部非递归操作的时间代价、递归调用的函数、递归调用的输入规模
• 联立所有递推式做消元，把多函数的递推关系转化为单个函数的递推关系，再用主定理、递归展开法等常规的递归复杂度计算方法求解即可

结合你给出的F1调用F2(N/2)的场景，我们基于该类问题的典型逻辑（即F2内部同样会调用规模折半的F1，且两个函数除递归调用外的其他操作都是常数时间O(1)）做推导：
首先列出递推式：

T1(n) = T2(n/2) + O(1)
T2(n) = T1(n/2) + O(1)

将第二个式子代入第一个式子，消去T2项可以得到：
T1(n) = T1(n/4) + O(1)
这个递推式对应的是每次递归输入规模缩小到1/4，每次递归的固定开销为常数，总递归次数为log_4 n，因此最终时间复杂度为O(log n)，你最初的猜测是正确的。

如果两个函数内部存在非O(1)的其他操作（比如遍历规模为n的数组），只需要把递推式中的常数项替换为对应操作的时间复杂度，再按同样逻辑联立求解即可。

内容的提问来源于stack exchange，提问作者AlexW00