Кто-нибудь может сказать мне, как сложность времени O (n * n!), А не o (n ^ n) для этой программы?

Question

Почему сложность времени составляет O(n*n!), а не o(n^n) для этой программы?

 void perm(String str, String prefix){
     if(str.length() == 0){
         System.out.println(prefix);
     } else{
        for(int i = 0; i < str.length(); i++){
           String rem = str.substring(0, i) + 
                           str.substring(i + 1);
           perm(rem, prefix + str.charAt(i));
       }
    }
 }

Answer 1

Это и то и другое. У нас есть

n! = 1 * 2 * ... * n <= 1 * n * ... * n = n^(n-1)

, поэтому n * n! = O(n^n). Теперь для малых o все выглядит немного иначе, потому что мы должны доказать, что для любого постоянного фактора c существует n, например, c * n * n! < n^n.

Но это не так уж сложно. Давайте выберем произвольный c, затем (для n>=3):

(n * n!)/(n^n) = n!/n^(n-1) = (n-1)!/n^(n-2) = 1/n * 2/n * ... * (n-1)/n < 
< 1/n * ((n-1)/n)^(n-3) <= 1/n

Итак, мы получили n * (n * n!) < n^n. Так что для нашего c мы можем просто выбрать n >= c, и мы в порядке. Таким образом, также n * n! = o(n^n). Таким образом, ваш алгоритм O(n * n!) и o(n^n).

Answer 2

Ответ в том, что строка становится короче.

Я предполагаю, что следующая программа без System.out

 void perm(String str, String prefix){
     if(str.length() == 0){
     } else{
        for(int i = 0; i < str.length(); i++){
           String rem = str.substring(0, i) + 
                           str.substring(i + 1);
           perm(rem, prefix + str.charAt(i));
       }
    }
 }

Предположим, строка содержит ноль символов. Тогда как среда выполнения - это оператор if, который равен O(1) = O(c).

. Для строки длиной n он злоупотребляет нотацией O(c1+n*c2*O(n-1)), чтобы проиллюстрировать рекурсию, где c2 - время выполнения для подстроки. Следовательно, время выполнения - O(n!) = O(n*n!), что, кстати. O(n^n) как O(n!) = O(n^n). Однако, вероятно, есть разница в маленьких обозначениях.