algorithm - 堆的算法时间复杂度

Question

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

我搜索了几个网站，答案都很模糊，其中一些人说时间复杂度是 O(N!) 一些人说它是 O(NlogN)。哪一个是正确答案？为什么？

谢谢你。

Answer 1

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

这些事实可以从维基百科页面上提供的递归算法中得出。本质上，代码交替交换和输出，因此每个输出都涉及一个交换。

但是，也有调用操作和循环测试。每次调用之前都有一个单循环测试，所以只需要统计调用的总数。

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

可以写成 Σ _0≤i≤n n !/ i ! 或 (Σ _0≤i≤n 1/ i !) n ! 或者 ( e -1)，大约是 1.71828 n！

Answer 2

我认为您在堆算法和堆排序算法或堆数据结构之间感到困惑。后两者的排序复杂度为 O(NlogN)。

您提到的算法用于生成所有排列，因为有 N! 每个 N 元素数组的排列，复杂度是 O(N!)。