Как проанализировать временную сложность следующего кода?

Question

Это O(n^6) или O(n!)?

public boolean isScramble(String s1, String s2) { 
    return isScramble(s1, 0, s1.length(), s2, 0); 
} 

private static boolean isScramble(String s1, int begin1, int end1,
                                  String s2, int begin2) { 
    final int length = end1 - begin1; 
    final int end2 = begin2 + length; 

    if (length == 1) return s1.charAt(begin1) == s2.charAt(begin2); 

    for (int i = 1; i < length; ++i) 
        if ((isScramble(s1, begin1, begin1 + i, s2, begin2) && 
             isScramble(s1, begin1 + i, end1, s2, begin2 + i)
            ) || 
            (isScramble(s1, begin1, begin1 + i, s2, end2 - i) && 
             isScramble(s1, begin1 + i, end1, s2, begin2))) 
           return true; 

    return false; 
} 

Анализ:

T(1) = 1
T(n) = (T(1) + T(n-1)) * 2 + (T(2) + T(n-2)) * 2 + ....
     =~ T(1) + T(2) + ... + T(n-1)

Answer 1

Попробуйте что-то вроде этого:

private static int ord = 1;

public boolean isScramble(String s1, String s2) { 
    boolean b = isScramble(s1, 0, s1.length(), s2, 0);
    System.out.println("The order is: " + [insert your classname here].ord);
    return b;
}

private static boolean isScramble(String s1, int begin1, int end1, String s2, int begin2) { 
ord++;
final int length = end1 - begin1;

Затем запустите его с увеличивающимися размерами (n) строки и запишите, как ord увеличивается с n.Это даст вам правильную нотацию.Обычно вы просто подсчитываете, сколько раз вызывается ваша рекурсивная функция.