有没有办法降低下面给出的函数的时间复杂度?

Question

这是计算非常大的数的阶乘的函数。这工作得很好，但时间复杂度相当高。如何降低时间复杂度?

这个函数被调用一次。当前查找100万的阶乘的时间是40000ms;期望时间:10 000ms

static void calcfactorial(unsigned int n)
{
unsigned int carry, i, j;
len = factorial[0] = 1;
for (i = 1; i < LEN; i++)
factorial[i] = 0;
for (i = 2; i <= n; i++)
{
carry = 0;
for (j = 0; j < len; j++)
{
factorial[j] = factorial[j] * i + carry;
carry = factorial[j] / 10;
factorial[j] = factorial[j] % 10;
}
while (carry)
{
factorial[len++] = carry % 10;
carry = carry / 10;
}
}
}

Answer 1

由于您只需要四倍的时间改进，以下内容可能就足够了:

• 使用更宽的(无符号)整数类型，如uint64_t。
• 不以十为基数计算，而是使用十的最大幂B，这样B•N适合整数类型¹，其中N是要计算其阶乘的数字。例如，对于64位整数和1,000,000!，你可以使用基数10¹³。
• 在进行乘法运算时，不要像循环for (j = 0; j < len; j++)那样乘以乘积数组中的每个数字。第一个数字之后的所有数字都以零开始，随着工作的进行，它们慢慢变为非零。跟踪最高的非零数字，并只进行到该数字的乘法，直到乘积进入下一位数字。
• 同样，由于在阶乘中积累了基数的因子，低位数随着工作的进行而变为零。跟踪最低的非零数字，并从那里开始工作。

下面是演示这些的程序。

在这个程序中一个重要的成本是按基数划分。如果您切换到2的幂的基数，这些就变成了位运算(除法的移位和余数的位与运算)，这要便宜得多。这将大大加快计算阶乘的速度。但是，最终的结果必须转换为十进制才能输出。这将比完全用十进制计算的成本更低，所以这是一个成功的方法。

之后，您可以在计算机科学堆栈交换中考虑这个答案。它建议将阶乘重组为质数的幂，并使用重复平方来计算质数的幂，然后将其相乘。

这个答案建议使用n!≈sqrt(2πn)•(n/e)ⁿ，这将需要更复杂的数学和编程。

脚注

¹使用十次幂的目的是可以直接从其基数B位数字中打印结果。

示范

#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

/*  Define T to be an unsigned integer type.  The larger the better up to the
widest type supported efficiently (generally the widest type for which the
processor has arithmetic instructions).
Define PRIuT to be a printf conversion specifier to print a type T as an
unsigned decimal numeral.
*/
typedef uint64_t T;
#define PRIuT   PRIu64  

//  Return the base-10 logarithm of x, rounded down.
static unsigned ilog10(T x)
{
unsigned log = 0;
for (; 10 <= x; x /= 10)
++log;
return log;
}

//  Return 10**x.
static T iexp10(unsigned x)
{
T power = 1;
for (; 0 < x; --x)
power *= 10;
return power;
}

int main(void)
{
//  Set the value we want the factorial of.
static const T N = 1000000;
//  Set the maximum value of T by using wrapping.
static const T MaximumT = -1;
/*  Determine the maximum number of decimal digits we can use easily:
Given a number with Digits decimal digits, Digits*N will be
representable in a T.
*/
unsigned Digits = ilog10(MaximumT/N);
/*  Set Base to 10**Digits.  This is the numerical base we will do
arithmetic in -- like base ten, but more efficient if it is bigger.
*/
T Base = iexp10(Digits);
/*  Set an array size that is sufficient to contain N!
For 1 < N, N! < N**N, so the number of digits in N! is less than
log10(N**N) = N * log(10).  Since we are using ilog10, which rounds
down, we add 1 to it to round up, ensuring we have enough room.
Then we divide that number of digits by the number of digits we will
have in each array element (and round up, by subtracting one before the
division and adding one after), and that is the number of array
elements we allocate.
*/
size_t S = (N * (ilog10(N)+1) - 1) / Digits + 1;
T *Product = malloc(S * sizeof *Product);
if (!Product)
{
fprintf(stderr,
"Error, unable to allocate %zu bytes.n", S * sizeof *Product);
exit(EXIT_FAILURE);
}
/*  Initialize the array to 1.  L and H remember the index of the lowest
and highest non-zero array element, respectively.  Since all the
elements before L or after H are zero, we do not need to use them in
the multiplication.
*/
Product[0] = 1;
size_t L = 0, H = 0;
//  Multiply the product by the numbers from 2 to N.
for (T i = 2; i <= N; ++i)
{
//  Start with no carry.
T carry = 0;
/*  Multiply each significant base-Base digit by i, add the carry in,
and separate the carry out.  We start separately with the lowest
non-zero element so we can track if it becomes zero.
*/
while (1)
{
T t = Product[L] * i + carry;
carry = t / Base;
if ((Product[L] = t % Base))    //  Leave when digit is non-zero.
break;
++L;    //  If digit is zero, increase L.
}
for (size_t j = L+1; j <= H; ++j)
{
T t = Product[j] * i + carry;
carry = t / Base;
Product[j] = t % Base;
}
//  If there is a final carry out, put it in a new significant digit.
if (0 != carry)
Product[++H] = carry;
}
/*  Print the result.  The first base-Base digit is printed with no
leading zeros.  All subsequent base-Base digits are printed with
leading zeros as needed to ensure exactly Digit decimal digits are
printed.
*/
printf("%" PRIuT, Product[H]);
for (size_t j = H; 0 < j--;)
printf("%0*" PRIuT, Digits, Product[j]);
printf("n");
free(Product);
}