为什么计算机在安排不同的排列时要花更多的时间？

Question

刚刚学习了heap的算法。对象的数量越多，系统将它们排列成所有可能的排列所花费的时间就越多。但是当我在计算器中计算该对象数量的阶乘时，结果是即时的。为什么会发生同样的情况。排列比计算阶乘需要更多时间？

   #include <stdio.h>
   #include <stdlib.h>
   #include<iostream>
    using namespace std;
    int len;
   void swap (int *x, int *y)
  {
     int temp;
     temp = *x;
     *x = *y;
     *y = temp;
  }
   void print(const int *v)
  {
     int i;
     int size = len;
     if (v != 0) {
     for ( i = 0; i < size; i++) {
     cout<< v[i] ;
}
cout<<'\n';
}
}
void heappermute(int v[], int n) {
int i;
if (n == 1) {
    print(v);
}
else {
    for (i = 0; i < n; i++) {
        heappermute(v, n-1);
        if (n % 2 == 1) {
            swap(&v[0], &v[n-1]);
    }
        else {
            swap(&v[i], &v[n-1]);
        }
   }
  }
 }

 int main()
 {
  int num[11];
  int  i;
  cout<<"How many numbers you want to enter: ";
  cin>>len;
  cout<<"\nEnter the numbers: ";
  for ( i = 0 ; i < len; i++)
   cin>>num[i];
  heappermute(num, len);
  return 0;
 }

Answer 1

您给计算机程序和计算器分配了两项不同的任务。生成一组对象的每个可能的排列与查找此类排列的数量是不同的问题。

十亿以下有多少个正偶数？这些是什么？（把它们都列出来。）哪一个需要更长的时间才能弄清楚？

除了列出所有可能性之外，还有其他方法可以计算阶乘。请参阅 this question，它给出了朴素的递归方法 (F(n) = n*F(n-1)) 这是Omega(n² log n) 和一个 O(n log n log log n)算法.

也可以估计一个阶乘，它可能足够接近。我不知道你的计算器使用的是什么方法，但一种可能是 Stirling's approximation.

为什么计算机在安排不同的排列时要花更多的时间？

Why computer takes more time in arranging different permutations?

sorting

permutation

c++11

heaps-algorithm