如何分析含循环的递归函数时间复杂度？以LeetCode143代码为例

问题描述 #

给定单链表的头节点，链表可表示为：
L₀ → L₁ → … → Lₙ₋₁ → Lₙ
需将链表重排为以下形式：
L₀ → Lₙ → L₁ → Lₙ₋₁ → L₂ → Lₙ₋₂ → …
注意不能修改节点值，仅可调整节点本身。

实现代码 #

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return; 
        }

        ListNode n1 = head;
        ListNode temp = null;

        while (n1.next.next != null) {
            n1 = n1.next;
        }

        temp = n1.next;
        n1.next = null;
        temp.next = head.next;
        head.next = temp;

        reorderList(temp.next);
    }
}

时间复杂度推导 #

你的直觉是对的，这段代码的时间复杂度确实是O(n²)，推导过程如下：

1. 第一次调用reorderList时，链表长度为n，循环while (n1.next.next != null)需要遍历n-1个节点才能找到倒数第二个节点，这部分操作是O(n)。
2. 完成第一次调整后，递归调用reorderList(temp.next)，此时传入的链表长度为n-2（已把最后一个节点移到第二个位置，剩下的待处理链表是原链表的第2到第n-1个节点）。
3. 第二次递归调用时，循环需要遍历(n-2)-1 = n-3个节点，操作是O(n-2)；以此类推，每次递归处理的链表长度减少2，循环的遍历次数也对应减少2。
4. 总操作数为：(n-1) + (n-3) + (n-5) + ... + 1。这是首项为n-1、末项为1、公差为2的等差数列，求和结果为(n²)/4（n为偶数）或(n²+1)/4（n为奇数），忽略常数系数后，时间复杂度为O(n²)。

如何确定带循环的递归函数的时间复杂度 #

可以按照以下步骤分析：

• 拆分单次调用的成本：先计算单次递归调用中，循环部分的时间复杂度，比如这段代码里单次调用的循环是O(k)，k是当前处理的链表长度。
• 梳理递归调用链：明确每次递归调用处理的问题规模变化，比如这里每次递归的问题规模从n变为n-2。
• 求和总操作数：把所有递归调用中的循环操作数加起来，得到总的时间开销，再推导渐近复杂度。
• 用递归式建模：也可以用递归表达式表示时间复杂度，比如这段代码的递归式为T(n) = T(n-2) + O(n)，边界条件是T(0)=T(1)=T(2)=O(1)。展开这个递归式就能得到总操作数，进而确定时间复杂度。

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