c++ - 大 O 表示法中的 next_permutation 时间复杂度

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;
   }

Answer 1

在最坏情况下，std::next_permutation 将排列转换为字典顺序中的下一个排列的复杂度为 O(n)。

n 个不同元素的排列数是 n!。数量permutations of multisets是 n!/(n1!*n2!*...*nk!) 其中 ni 是 i 类型的相等元素的数量.

我们有两种不同的情况:

1. 不同的数字(集合)。

   当所有元素都不同时，

   next_permutation 通常(如果不总是)用 O(1) 摊销时间实现。后者意味着 next_permutation 在多次调用时的平均时间为 O(1)。

   在这种情况下，permutationSort 函数的复杂度在最坏情况下为 O(n!)，因为 n!使用 next_permutation 的分期 O(1) 调用进行循环迭代。

2. 有重复的数字(多集)

   在这种情况下，next_permutation 无法保证 O(1) 摊销的复杂性，但“多集排列”的数量可能远小于 n !。 permutationSort 函数复杂度的上限在最坏情况下为 O(n!*n)。我想它可以减少到 O(n!) 但不知道如何证明这个事实。