擅长:python、mysql、java
<p>我相信有证据表明运行时确实是<code>O(n*n!)</code>。在</p>
<p>(灵感来自前面的一个问题:<a href="https://stackoverflow.com/questions/5363619/complexity-of-recursive-string-permutation-function">complexity of recursive string permutation function</a>)</p>
<p>对于所花费的时间,我们有以下递归,无需打印:</p>
<p><code>T(n) = n*T(n-1) + O(n^2)</code></p>
<p>现在如果<code>U(n) = T(n)/n!</code>那么我们必须得到它</p>
<p><code>U(n) = U(n-1) + O(n^2/n!)</code></p>
<p>这是一个伸缩系列。在</p>
<p>因此我们得到</p>
<p><code>U(n) = U(1) + 2^2/2! + 3^2/3! + ... + n^2/n!</code></p>
<p>使用<code>e^x</code>的幂级数,乘以x几次微分,我们看到<code>2^2/2! + 3^2/3! + ... + n^2/n! = O(1)</code></p>
<p>因此</p>
<p><code>T(n) = O(n!)</code>。在</p>
<p>这是没有印刷的时间。在</p>
<p>因此,打印的总时间是<code>O(n * n!)</code>。在</p>
<p>这也证明了<code>sorted</code>等的运行时间是多少并不重要,只要它们是多项式的,该算法都是渐近最优的。在</p>
<p>常数可能是错误的,这正是处理<code>n*n!</code>时的实际问题。在</p>