Объясните временную сложность перестановок, используя математическое выражение ⇐ JAVA

[Anonymous]

Это мой код для вычисления всех перестановок входного массива.

Код: Выделить всё

public class Permutations {
public static void main(String[] args) {
int[] a = {3, 1, 4};
permutations(a, new int[a.length], new ArrayList());
}

private static void permutations(int[] a, int[] map, List ds) {
if(ds.size() == a.length) {
System.out.println(ds);
return;
}

for(int i = 0; i < a.length; i++) {
if(map[i] != -1) {
ds.add(a[i]);
map[i] = -1;
permutations(a, map, ds);
ds.remove(ds.size()-1);
map[i] = 0;
}
}
}
}

Мне хотелось узнать временную сложность этой программы, поэтому я решил решить ее с помощью математического выражения:

Код: Выделить всё

T(n) = n*T(n-1)
= n*[(n-1)*T(n-2)]
= n*(n-1)*(n-2)*--*T(0)
= n!

Итак, я понял! используя мое математическое выражение, но я вижу больше рекурсивных вызовов в рекурсивном дереве.
Для n = 3, n!= 6, где рекурсивное дерево имеет 15 рекурсивных вызовов. p>


Справка мне, как правильно решать временную сложность, используя математические выражения.

Подробнее здесь: https://stackoverflow.com/questions/791 ... expression