堆的算法时间复杂度

Question

任何人都可以告诉我维基百科,https: //en.wikipedia.org/wiki/Heap%27s_algorithm中显示的这个Heap算法的时间复杂度究竟是什么？

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

谢谢.

Answer 1

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

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

Answer 2

有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 ñ!/ 我!或(_Σ0≤i≤n1/i!)n!或(e -1),约为1.71828 n!