如何计算Post_to_PreOrder算法的时间复杂度？

问题描述 #

我需要计算以下算法的时间复杂度，目前仅推测出最坏情况（即每次所有元素都进入一个数组，另一个数组为空）。根据所学，需分析最坏、最好及平均情况，但无法推导复杂度函数，也不确定自己假设的最坏情况是否正确，希望获得此类问题的通用处理技巧，并得到该算法复杂度的分析及推导过程。

算法代码 #

public class Test {
    // 测试输入，用于验证算法运行正确性
    static char[] pin = {'A','B','C','D','E','F','G','H'};
    
    public static void Post_to_PreOrder(char[] P, int first, int last){
        System.out.println(P);
        if (first <= last){
            System.out.println(P[last]);
            int i = 0;
            while (P[i] < P[last]){
                i++;
            }
            int k = i;
            char[] m =  new char[k];
            for (i = 0; i < k; i++){
                m[i] = P[i];
            }
            char[] M = new char[P.length - k - 1];
            for (i = k; i < P.length - 1; i++){
                M[i-k] = P[i];
            }
            Post_to_PreOrder(m, 0, m.length-1);
            Post_to_PreOrder(M, 0, M.length-1);
        }
    }

    public static void main(String[] args){
        Post_to_PreOrder(pin, 0, pin.length-1);
    }
}

时间复杂度分析通用技巧 #

• 聚焦递归核心逻辑：先明确每次递归调用的非递归工作量，再分析子问题的划分比例
• 优先用递归树法或主定理：递归树直观展示每层总工作量，主定理适合形如 T(n) = aT(n/b) + f(n) 的递归式
• 明确边界触发条件：最坏/最好情况通常由输入数据的有序性、划分的均衡性决定
• 平均情况需假设输入概率分布：默认元素随机排列，计算期望复杂度

该算法的复杂度分析 #

算法逻辑梳理 #

这是一个从后序遍历序列推导前序遍历的递归算法：

1. 取当前数组最后一个元素作为根节点
2. 将数组划分为左子树（所有小于根的元素）和右子树（剩余元素）
3. 递归处理左右子树

设 T(n) 为处理长度为 n 的数组的时间复杂度（n=0 时 T(0)=O(1)），每次递归的非递归工作量为 O(n)（遍历找划分点+复制子数组），因此递归式为：
T(n) = T(k) + T(n-k-1) + O(n)，其中 k 是左子数组的长度

最坏情况 #

触发条件

输入数组为严格递增/递减序列：

• 严格递增时，根节点是最大元素，所有元素均小于根，左子数组长度为 n，右子数组为空（代码存在数组长度为负的bug，但逻辑上对应右子树无元素）
• 严格递减时，根节点是最小元素，所有元素均大于根，右子数组长度为 n-1，左子数组为空

复杂度推导

递归式简化为：T(n) = T(n-1) + O(n)
展开累加：
T(n) = O(n) + O(n-1) + ... + O(1) = O(n²)

最好情况 #

触发条件

每次划分后左右子数组长度尽可能均衡（接近 n/2），比如输入是平衡二叉树的后序遍历序列。

复杂度推导

递归式简化为：T(n) = 2T(n/2) + O(n)
用主定理：a=2，b=2，f(n)=O(n)，n^log_b a = n，与 f(n) 同阶，因此：
T(n) = O(n log n)

平均情况 #

假设前提

输入元素随机排列，左子数组长度 k 服从 0~n-1 的均匀分布（每个长度的概率为 1/n）。

复杂度推导

平均期望复杂度 E[T(n)] 满足：
E[T(n)] = 2*(1/n)*Σ_{k=0}^{n-1}E[T(k)] + O(n)

通过递推化简（两式相减消去求和项），最终得到：
E[T(n)] = O(n log n)

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