java - 这个程序在最坏情况下的递归方程是什么？

Question

这是程序：

public class Program {
    public enum T { MIN, MAX } ;
    
    public static int mystery(int[] arr, int d, int f, T k ) {
        int answer = d ;
        if( d < f ) {
            int middle = ( d + f ) / 2 ;
            
            int max = mystery( arr, d, middle, T.MAX ) ;
            int min = mystery( arr, middle + 1, f, T.MIN ) ;
            
            if( k == T.MAX ) {
                answer = min ;
            } else {
                answer = max ;
            }
        }
        return answer ;
    }
    
    public static void main( String [ ] arg ) {
        int [ ] t = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } ;
        System.out.println( mystery( t, 0, t.length - 1, T.MAX ) ) ;
    }
}

程序输出：5。

如果 arr 的大小为 n，我尝试以这种方式计算递归方程。我们对该函数有两次调用，所以它是T(n) = 2 T(...) + ..... 我们可以注意到，每次数组除以 2 所以我们可以说T(n) = 2 T(n/2) + ....

然后，既然我们有if (k == T.MAX) ... ，我们可以知道它在每次调用中运行 1 次，所以它在 O(1) 中。那么等式是T(n) = 2 T(n/2) + 1正确的吗？

标签： javaalgorithmrecursiontime-complexity