c – 计算大因子时间复杂度
|
我遇到了一个问题,我需要计算非常大的阶乘的值.我以两种不同的方式在C中解决了这个问题,但只想知道我的复杂性分析是否准确.
在任一方法中,我表示非常大的数字作为向量,其中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! 写出完整的总结应该给出： 似乎这两种方法的渐近复杂性是相同的,因为我的计算是准确的.这是真的？ 解决方法
您提供的要点中的功能的复杂性是O(log10n！),其中n是您传递给该方法的数字.
从代码的第一部分可以看出这一点的推理： 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进位) 这将功能的复杂度提高到O(klog10n！),其中k！ = n,因此整个代码的复杂度现在是O(k2log10k！) （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |