快速阶乘运算 |
您所在的位置：网站首页 › 双阶乘计算方法 › 快速阶乘运算 |
快速阶乘运算
|
在前一篇blog中提到了logn复杂度求出C(n,r)，利用此结果在(logn)^2复杂度下计算n! oh, fuck!!! 校园招聘微软的三面面试官出了这道bug题。。。 分析：利用下面的公式可以降低复杂度
由于C(n, n/2)需要logn复杂度计算出来，加上n!所需的logn，所以总体复杂度为(logn)^2，代码如下： #include #include #include using namespace std; #define MAXSIZE 100 unsigned long answer[MAXSIZE]; unsigned long long int power(unsigned long base, unsigned long exp) { unsigned long long int result = 1; while (exp) { if (exp & 0x01) result *= base; base *= base; exp >>= 1; } return result; } unsigned long cn2(unsigned long n) { unsigned long x = (1 ((n >> 1) * n)) & mask; } unsigned long factorial(unsigned long n) { unsigned long temp; if (n == 1) return 1; else if (n & 0x01 == 1) return n * factorial(n - 1); else { temp = factorial(n >> 1); return cn2(n) * temp * temp; } } void main() { int number = 4; unsigned long result = factorial(number); cout > ((m >> 1) * p_size)) & mask; } return temp; } unsigned factor(unsigned long n) { unsigned long temp; if (n == 1) return 1; else if (n & 0x01 == 1) return n * factor(n - 1); else { temp = factor(n >> 1); return cnrs[number++] * temp * temp; } } unsigned long factorial(unsigned long n) { unsigned long x = (1 |
【本文地址】