设计一个算法时间复杂度为O(n),求1!+2!+…+n!,写出一个代码用c语言
时间: 2024-09-13 15:03:19 浏览: 46
算法时间复杂度的计算.doc
设计一个计算1!到n!之和的时间复杂度为O(n)的算法,可以采用动态规划的思想,因为连续阶乘的增长速度非常快,所以直接累加会很快达到大数溢出的问题。我们可以只存储前两个结果,然后每次更新当前结果时只需要考虑前两个已知的结果。以下是C语言的一个代码示例:
```c
#include <stdio.h>
long long factorial_sum(int n) {
if (n <= 1)
return n;
long long fact1 = 1, fact2 = 2; // 初始化前两个阶乘值
long long sum = fact1 + fact2; // 初始总和为1! + 2!
for (int i = 3; i <= n; i++) {
long long next_fact = fact1 * i; // 计算下一个阶乘
sum += next_fact; // 更新总和
fact1 = fact2; // 更新fact1为之前的fact2
fact2 = next_fact; // 更新fact2为新的next_fact
}
return sum;
}
int main() {
int n;
printf("Enter a number: ");
scanf("%d", &n);
long long result = factorial_sum(n);
printf("The sum of factorials from 1! to %d! is: %lld\n", n, result);
return 0;
}
```
这个算法避免了直接计算每个阶乘,所以空间复杂度为O(1),时间复杂度为O(n)。
阅读全文