有人能告诉我维基百科中展示的Heap算法的时间复杂度到底是什么吗？https://en.wikipedia.org/wiki/Heap%27s_algorithm
我搜索了几个网站，答案都含糊不清，有些说时间复杂度是O(N!)，有些则说是O(NlogN)。哪一个才是正确的答案？为什么？
谢谢。
2个回答
9
总共有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≤nn!/i!或(Σ0≤i≤n1/i!)n!，或(e-1)，它约为1.71828 n!。
这些事实可以从维基百科页面上提供的递归算法中推导出来。本质上，代码交替进行交换和输出，因此每个输出涉及一个交换。
然而，还有调用操作和循环测试。在每次调用之前只有一个循环测试，因此只需要计算总调用次数。
在最坏的情况下，在输出之前会有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.71828 n!。
- rici
2
谢谢您的清晰解释。但我可以知道为什么会出现这个算法吗？这个算法比其他找到所有可能排列的方法更好，还是只是另一种新的探索方式？谢谢。 - nightowl_nicky
@USER1223_T：我认为这在维基百科页面上已经解释得很清楚了。（“该算法最小化运动。”）我怀疑那个想出这个算法的人只是觉得它很酷；那已经是50多年前的事情了，所以我不知道我们是否会得到答案。我认为这是一个很酷的算法，值得一提。 - rici
6
我觉得你混淆了Heap算法和堆排序算法或堆数据结构。后两者的排序复杂度为O(NlogN)。
你提到的算法是用于生成所有排列的，因为每个N元素数组有N!个排列，所以其复杂度为O(N!)。
- lazyc97
1
我明白了，谢谢你的解释。但是为什么他们要开发这个找到所有排列的算法，因为时间复杂度仍然是O(N!)？如果与其他方法（普通查找所有排列的方法）相比，这个算法是否更有效率？ - nightowl_nicky
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接