在任一方法中,我表示非常大的数字作为向量,其中v [0]表示最低有效数字,最后一个索引处的值表示最高有效数字.版本1的代码可以在这个gist中找到.
给定上述代码,似乎multiplyVectorByInteger()是O(log(n * k)),其中n是给定的整数,k是由向量表示的数字.我的逻辑是,我们将要做一些与结果数n * k的长度成比例的步骤,以便产生一个表示n * k的向量. n * k的长度为O(log(n * k))一些步骤将在for循环中执行,其他步骤在以下while循环中执行.
在这个程序中找到大因子,每当我们调用multiplyVectorByInteger(),我们将传递一个整数n和(n-1)！的向量表示.这意味着如果我们要找到6！,我们传递整数6和向量表示5！该函数将返回6！的向量表示.使用以前的信息,我相信我可以说复杂度是O(log(i！)),其中我是整数传递.为了找到大因子,我们必须将这个方法称为O(n)次,其中n是我们试图找到的阶乘.我们积累的逻辑将如下所示：
1! = 1! 1!*2 = 2! 2!*3 = 3! 3!*4 = 4! ... (n-1)!*n = n!
因为在每个级别我们都在计算i！,所以我们在每个级别执行O(log(i！))步骤.总结如下：
我的逻辑从第二个总和跳转到大呵呵的符号如下：打破这一点我们得到以下内容：
1log(1) + 2log(2) + 3log(3) + ... + nlog(n)
很明显,我们得到log(1)log(2)… log(n)的O(n ^ 2)项.日志规则提醒我们,log(a)log(b)= log(ab),这意味着这种情况下的日志条件会崩溃到log(n！).因此,我们有O(n ^ 2)log(n！).
这将使这个程序O(n ^ 2log(n！))的整体时间复杂度.这个分析是否正确？
朴素的时间复杂度
为了练习复杂性分析,我想看看似乎是一个效率较低的解决方案.假设我们改变了multiplyVectorByInteger()函数,使得不用在O(log(n！))时间内将k的向量表示乘以整数n来产生n！,新的multiplyVectorByIntegerNaive()函数将数字的向量表示共计n次.
multiplyVectorByIntegerNaive()存在于此gist.它使用一个函数addVectors(),其复杂度为O(n),其中n个大小的两个向量中较大的一个.
很明显,我们仍然在调用这个新的乘法函数n次,但是我们需要看复杂度是否已经改变.例如给定整数6和向量表示5！我们加5！ 5！ 5！ 5！ 5！ 5！得到6 * 5！ = 6！如果给定的整数与我们的乘法函数是i,那么很明显我们做了i-1的补充.我们可以枚举上一个例子调用我们的初始乘法函数的步骤.
5! + 5! 2*5! + 5! 3*5! + 5! 4*5! + 5! 5*5! + 5!
写出完整的总结应该给出：
似乎这两种方法的渐近复杂性是相同的,因为我的计算是准确的.这是真的？
解决方法
从代码的第一部分可以看出这一点的推理：
for (int i = 0; i < numVector.size(); ++i) {
returnVec[i] = (numVector[i]*n + carry) % 10;
carry = (numVector[i]*n + carry) / 10;
}
传递的numVector代表(n-1)！即它包含构成该数字的所有数字.但是这个数字的长度只是⌈log10((n-1)！)⌉.你可以从一个简单的例子中看到这一点：
如果(n-1)！是100,那么numVector的长度将为3,与⌈log10100⌉= 3相同.
同样的逻辑也适用于while循环：
while (carry) {
returnVec.push_back(carry%10);
carry /= 10;
}
由于进位值不会大于n(您可以自己证明这一点),那么这个循环运行的最大次数也不会大于⌈log10n！⌉,那么函数的总体复杂度是等价的到O(log10n！).
因此,要计算k !,你的代码(包括main)的复杂度将是O(klog10k！)
天真版
对于天真的版本,唯一改变的是现在的方法是手动加载乘法的形式.这是通过明确地将每个值乘以n而跳过的其他版本
(numVector [i] * n进位)
