任何人都可以解释如何计算以下算法的复杂度吗？

Question

我有这个算法，我必须找到它的复杂性。我想到了一些事情，但直到现在我发现的唯一复杂性是“最坏”的情况，我认为每次所有元素都进入一个数组而另一个是空的。

public class Test {
    //this input served as an example to find out if the algorithm is running correctly 
    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);
    }
}

从我到目前为止所学的内容来看，为了找到算法的复杂性，我们必须检查最坏、最好和“平均”情况（抱歉，如果命名有误，我是从希腊语翻译过来的），不包括以下情况提供了哪个功能。在这种情况下，我找不到复杂的函数，所以我想我一直在检查案例。但为了确保我的“最坏”情况实际上是最坏的，我必须证明这一点。这是希望你们进来给我一些提示，告诉我如何处理这些类型的问题，也许是这个问题的答案，解释解决方案背后的原因？提前谢谢大家！

Answer 1

您提供的算法是将后缀表达式转换为前缀表达式的递归实现，其中后缀表达式作为字符数组给出。该算法的工作原理是递归地将后缀表达式拆分为两个子表达式，直到剩下一个字符，然后在每次递归调用时反转子表达式和运算符的顺序以获得相应的前缀表达式。

算法的时间复杂度可以分析如下：

1. 递归的基本情况是子表达式包含 只有一个字符，这需要恒定的时间

   O(1)

   来处理。
2. 一般情况下，算法会拆分后缀表达式 根据最后一个字符的位置分成两个子表达式 在后缀表达式中。查找位置的循环 最后一个字符需要

   O(n)

   时间，其中 n 是字符的长度 子表达式。
3. 然后算法通过复制 将原始子表达式中的字符放入两个新数组中。 这总共需要

   O(n)

   时间，其中 n 是原始文件的长度 子表达式。
4. 算法然后递归地调用自己在两个新的 子表达式，这会导致两个较小的子问题，即 每个都是原始问题大小的一小部分。的时间复杂度 因此，每个递归调用都与 子问题，在平均情况下由

   (n/2)

   给出。
5. 递归一直持续到到达基本情况，此时 点子表达式的长度为1，递归返回 备份调用堆栈。

算法的总时间复杂度可以表示为一个递归函数：

T(n) = 2T(n/2) + O(n)

其中

T(n/2)

是每次递归调用的时间复杂度，

O(n)

是拆分和复制操作的时间复杂度。这是一个标准的分而治之算法，其时间复杂度可以使用主定理求解，给出：

T(n) = O(n log n)

因此，给定算法的时间复杂度为

O(n log n)

，其中n为输入后缀表达式的长度。