0

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

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

1 回答 1

4

你给你的计算机程序和你的计算器两个不同的任务。生成一组对象的每一个可能的排列是一个与找到这种排列的数量不同的问题。

十亿以下有多少个正偶数?这些是什么?(全部列出。)哪一个需要更长的时间才能弄清楚?

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

也可以估计一个阶乘,它可能足够接近。我不确切知道您的计算器使用的是什么方法,但一种可能性是斯特林的近似值

于 2016-01-30T06:55:45.217 回答