计算大因子时间复杂度

Question

我遇到了一个问题,我需要计算非常大的因子的值.我用两种不同的方式在C++中解决了这个问题,但只想知道我的复杂性分析是否准确.

在任何一种方法中,我将非常大的数字表示为v[0]表示最低有效数字的向量,而最后一个索引处的值表示最高有效数字.版本1的代码可以在这个要点中找到.

鉴于上面的代码,它似乎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!))在每个级别执行步骤.总结如下:

我从第二次总结跳到Big-Oh表示法的逻辑如下......打破这个我们得到以下结果:

1log(1) + 2log(2) + 3log(3) + ... + nlog(n)

很明显我们得到的O(n^2)条款log(1) + log(2) + ... + log(n).日志规则提醒我们log(a) + log(b) = log(ab),这意味着此案例中的日志条款会崩溃log(n!).因此,我们有O(n^2)log(n!).

这将使该计划的总体时间复杂性O(n^2log(n!)).这个分析是否正确？

天真的版本时间复杂性

为了练习复杂性分析,我想看一下效率较低的解决方案.假设我们改变我们的multiplyVectorByInteger()功能,从而替代的矢量表示乘以k一个整数n的O(log(n!))时间来产生n!,新的multiplyVectorByIntegerNaive()功能增加了许多共同共有的向量表示n时间.

multiplyVectorByIntegerNaive()存在于这个要点中.它利用了一种函数,addVectors()其复杂性O(n)在两个向量中较大的n个大小.

很明显,我们仍然称这个新的乘法函数为n时间,但我们需要看看复杂性是否已经改变.例如,给定整数6和向量表示5!我们添加5! + 5! + 5! + 5! + 5! + 5!到get 6*5! = 6!.如果我们的乘法函数的给定整数是i,我们很清楚我们做了i-1添加.我们可以枚举前一个示例调用我们的朴素乘法函数的步骤.

5! + 5!
2*5! + 5!
3*5! + 5!
4*5! + 5!
5*5! + 5!

写出完整的总和现在应该给出:

考虑到我的计算是准确的,两种方法的渐近复杂度似乎是相同的.这是真的？

Answer 1

您提供的要点中函数的复杂性是，其中O(log10n!)n是您传递给该方法的数字。

\n\n

从代码的第一部分可以明显看出其原因：

\n\n

for (int i = 0; i < numVector.size(); ++i) {\n    returnVec[i] = (numVector[i]*n + carry) % 10;\n    carry = (numVector[i]*n + carry) / 10;\n}\n

\n\n

传入numVector的代表(n - 1)!. 即它包含组成该数字的所有数字。然而该数字的长度很简单\xe2\x8c\x88log10((n-1)!)\xe2\x8c\x89。您可以从一个简单的示例中看到这一点：

\n\n

如果(n-1)!是 100，那么 的长度numVector将为 3，与\xe2\x8c\x88log10100\xe2\x8c\x89 = 3。

\n\n

同样的逻辑也适用于 while 循环：

\n\n

while (carry) {\n    returnVec.push_back(carry%10);\n    carry /= 10;\n}\n

\n\n

由于 的值carry不会大于n（你可以自己证明这一点），那么这个循环运行的最大次数也不会大于，那么函数的总复杂度相当于\xe2\x8c\x88log10n!\xe2\x8c\x89O(log10n!)。

\n\n

因此，要计算k!，您的代码（包括主代码）的复杂度将为O(klog10k!)

\n\n

天真的版本

\n\n

对于天真的版本，唯一改变的是现在该方法以加法的形式手动逐步执行乘法。这是其他版本通过显式地将每个值乘以而跳过的事情n

\n\n

(numVector[i]*n + carry)

\n\n

这将函数的复杂性增加到，因此整个代码的复杂性现在为O(klog10n!)k! = nO(k2log10k!)

\n