堆算法时间复杂度

本文介绍了堆算法时间复杂度的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

谁能告诉我，维基百科 https:中显示的该堆算法的时间复杂度到底是多少?//en.wikipedia/wiki/Heap%27s_algorithm 吗?

can anyone tell me what exactly is the time complexity of this Heap's algorithm shown in wikipedia, en.wikipedia/wiki/Heap%27s_algorithm ?

我搜索了几个网站，答案都含糊不清，其中一些人说时间复杂度为O(N！)，有些人说这是O(NlogN).正确的答案是哪一个?为什么呢?

I searched several websites and the answers are all vague, some of them say the time complexity is O(N!) some of them say it's O(NlogN). Which one is the correct answer? And why?

谢谢.

推荐答案

有 N ！全部排列并生成所有排列需要Θ( N ！)时间和Θ(N)空间.换句话说，每个排列需要摊销Θ(1)时间.

There are N! permutations in all and generating all of them requires Θ(N!) time and Θ(N) space. In other words, each permutation requires amortised Θ(1) time.

这些事实可以从Wikipedia页面上提供的递归算法中得出.本质上，该代码交替交换和输出，因此每个输出都包含一个交换.

Those facts can be derived from the recursive algorithm presented on the Wikipedia page. In essence, the code alternates swaps and outputs so each output involves a single swap.

但是，也有调用操作和循环测试.每个调用之前都有一个循环测试，因此只需要计算调用总数即可.

However, there are also call operations and loop tests. There is a single loop test before each call, so it is only necessary to count the total number of calls.

在最坏的情况下，在输出之前将有 n 个递归调用.但这仅发生一次，在算法的最开始.使用参数 n 的单个调用将生成 n ！输出.它通过 n 个递归调用来做到这一点，每个递归调用都产生( n -1)！输出，并进行( n -1)个递归调用，因此有 n ( n -1)个调用带有参数 n -2.依此类推，总共有1 + n + n ( n -1)+ n ( n -1)( n -2)+ ... + n ！电话.

In the worst case, there will be n recursive calls before an output. But that only happens once, at the very beginning of the algorithm. A single call with argument n produces n! outputs. It does that with n recursive calls, each of which produces (n-1)! outputs, and does (n-1) recursive calls, so there are n(n-1) calls with argument n-2. And so on, so there are a total of 1 + n + n(n-1) + n(n-1)(n-2) + ... + n! calls.

可以写为Σ 0≤ i≤ n n ！/ i ！或(Σ 0≤ i≤ n 1/ i ！) n ！或( e -1)，即大约1.71828 n ！

That can be written as Σ0≤i≤nn!/i! or (Σ0≤i≤n1/i!)n! Or (e-1), which is approximately 1.71828 n!