下一个排列的时间复杂度（用大 O 表示法）

Question

据我所知，std::next_permutation算法的时间复杂度为O(n!)。有人能解释一下为什么吗？或者说我是否正确？

以下是我正在运行的代码，尝试计算给定数组（大小为n）被排序前需要进行多少次排列操作：

int permutationSort(int a[], int n)
   {
      int count = 0;

      while (next_permutation(a, a + n))
      {
          count++;
      }

      return count;
   }

- kman123

---

这个std::next_permutation的参考文献有帮助吗？ - Some programmer dude

它必须是Omega(n!)，因为它枚举了所有n!个排列？但标准并不保证O(1)摊销复杂度。 - Niklas B.

你似乎混淆了 next_permutation 的时间复杂度和使用 next_permutation 进行排序的时间复杂度。 - Jarod42

一个大小为n的序列的排列数量（不包括重复排列）是n!（第一个元素有n种可能性，第二个有n-1种，然后... -> n * (n-1) * .. * 2 * 1 -> n!）。在这里，您需要迭代直到序列排序，因此最多调用n!次next_permutation。 - Jarod42

@kman123 最坏情况是 O(n * n!)（需要 n! 次调用 next_permutation），最好情况是 O(n)，即只需一次调用 next_permutation（当 a 已经是最后一个排列时）。 - Holt

Answer 1

std::next_permutation函数的复杂度是O(n)，它可以将排列转换为按字典序的下一个排列。

有n个不同元素的排列数是n!。有多重集合的排列数是n!/(n1!*n2!*...*nk!)，其中ni是类型i的相同元素的数量。

我们有两种不同的情况：

1. 不同的数字（集合）。

   当所有元素都不同的时候，next_permutation通常（如果不总是）使用O(1)摊销时间实现。后者意味着当连续调用多次时，next_permutation的平均时间是O(1)。

   在这种情况下，由于n!次循环迭代和摊销的O(1)调用next_permutation，您的permutationSort函数的复杂度在最坏情况下是O(n!)。

2. 具有重复的数字（多重集合）

   在这种情况下，next_permutation没有保证的O(1)摊销复杂度，但是“多重集合的排列”数可能比n!小得多。您的permutationSort函数的复杂度上限在最坏情况下是O(n!*n)。我认为它可以降低到O(n!)，但不知道如何证明这个事实。

- DAle

---

如果参数没有重复元素，则 std::next_permutation 的参考实现的摊销常数时间为常数时间，此时总运行时间为 O(n!)。如果参数有 O(n) 个重复元素，则无法保证摊销常数时间，但排列的总数较少，分析也更加复杂。 - rici

@rici，是的，不知道我怎么会忽略这个事实。 - DAle

Answer 2

你的例子并没有测量关于std::next_permutation的工作原理的任何内容，它只是测量了调用次数。你确实有O(n!)次对std::next_permutation的调用。

你需要查看参考文献以找到你没有源代码的代码的复杂度。或者你可以构造一个计算交换和比较次数的类型，以获得经验性的复杂度度量。这不是一种分析，但提供了类似的信息。

- Caleth