时间戳

首页 > 解决方案 > 谁能告诉我这个程序的时间复杂度是 O(n*n!) 而不是 o(n^n)？

algorithm - 谁能告诉我这个程序的时间复杂度是 O(n*n!) 而不是 o(n^n)？

问题描述

为什么这个程序的时间复杂度是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));
       }
    }
 }

标签： algorithmbacktracking

解决方案

两者兼而有之。我们有

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)。

推荐阅读