Heap的算法时间复杂度
Heap's algorithm time complexity
谁能告诉我维基百科中显示的堆算法的时间复杂度究竟是多少，https://en.wikipedia.org/wiki/Heap%27s_algorithm？
我查了好几个网站，答案都是模糊的，有的说时间复杂度是O(N!)，有的说是O(NlogN)。哪一个是正确答案？为什么？
谢谢。
我认为您混淆了堆算法和堆排序算法或堆数据结构。后两者的排序复杂度为O(NlogN)。
你说的算法是生成所有排列的，因为有N！每个 N 元素数组的排列，复杂度为 O(N!)。
有N个！全部排列并生成所有排列需要 Θ(N!) 时间和 Θ(N) space。换句话说，每个排列都需要摊销 Θ(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≤nn!/i ！或 (Σ0≤i≤n1/i!)n!或(e-1)，约等于1.71828n!
谁能告诉我维基百科中显示的堆算法的时间复杂度究竟是多少，https://en.wikipedia.org/wiki/Heap%27s_algorithm？
我查了好几个网站，答案都是模糊的，有的说时间复杂度是O(N!)，有的说是O(NlogN)。哪一个是正确答案？为什么？
谢谢。
我认为您混淆了堆算法和堆排序算法或堆数据结构。后两者的排序复杂度为O(NlogN)。
你说的算法是生成所有排列的，因为有N！每个 N 元素数组的排列，复杂度为 O(N!)。
有N个！全部排列并生成所有排列需要 Θ(N!) 时间和 Θ(N) space。换句话说，每个排列都需要摊销 Θ(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≤nn!/i ！或 (Σ0≤i≤n1/i!)n!或(e-1)，约等于1.71828n!